Robertson–Seymour theorem

From Wikipedia, the free encyclopedia

In graph theory, the Robertson–Seymour theorem (also called the graph minors theorem) states that, in any infinite class of finite, undirected, unlabelled graphs, there are two such that one is a contraction of a subgraph (i.e., a minor) of the other. Another way to state the theorem is that, for every family F  of (unlabeled, finite) graphs, such that if a graph is in the family then all its minors also are, there is a finite class O  of finite graphs such that a graph G  is in F  if and only if no member of O  is a minor of G . The members of O  are called the excluded minors (or forbidden minors, or minor-minimal obstructions) for the family F . The significance of the theorem is the finiteness of the set of excluded minors.

The statement is a generalisation of a version of Kuratowski's theorem on planar graphs due to the German mathematician Klaus Wagner. Neil Robertson and Paul D. Seymour called it Wagner's conjecture (although Wagner said he never conjectured it) until they proved it in a series of twenty papers spanning over 500 pages from 1983 to 2004.

A weaker result for trees is implied by Kruskal's tree theorem, which was proved in 1960.

[edit] Statement

A more formal statement of the Robertson–Seymour theorem is that the minor ordering on finite, undirected, unlabelled graphs is a well-quasi-ordering. This means that every infinite sequence of finite undirected graphs contains an infinite nondecreasing subsequence.

This statement can be reformulated as a statement about the finiteness of obstructions to membership in families of graphs that are downwardly closed according to the minor ordering: For every (possibly infinite) set of graphs that is downwardly closed there is a finite set of graphs, called its obstruction set, such that a graph is in the set if and only if none of its minors is in the obstruction set.

The primary concepts involved in the statement of the theorem are as follows:

• A graph H is a minor of a graph G if H is isomorphic to a graph obtained from G by contracting edges, deleting edges, and deleting isolated nodes;
• The minor ordering of graphs is that defined by H ≤ G if H is a minor of G.

Robertson-Seymour theorem: For every infinite sequence of finite undirected graphs G₁, G₂, G₃, ..., there exist positive integers i and j, such that i < j and G_i  ≤  G_j. Equivalently, if a sequence of finite undirected graphs is such that no element is a minor of a later element, then the sequence is finite.

This theorem may be reformulated in terms of the following concept:

A set that is closed downward: if G is in S, all its minors, such as H, are in S as well.

• A set S of graphs is downwardly closed with respect to the minor ordering if, whenever G S and H is a minor of G, then H S.

The following sets of finite graphs are downwardly closed:

• The set of all graphs that are disjoint unions of paths.
• The set of all forests.
• The set of all planar graphs.
• The set of all outerplanar graphs.
• The set of all graphs that can be embedded without self intersections in a torus.
• the set of all graphs that can be embedded without self intersections in a fixed arbitrary surface S.
• the set of all graphs that are knotlessly embeddable in Euclidean 3-space.
• the set of all graphs that are linklessly embeddable in Euclidean 3-space.

An obstruction set: the elements not in the set are those greater than or equal to a forbidden minor.

A trivial consequence of the definition of downwardly closed sets is that every such set has an obstruction set, which is a set of graphs called forbidden minors or excluded minors: a graph is in the set if and only if none of its minors is a forbidden minor. The Robertson–Seymour theorem states that every downwardly closed set has a finite obstruction set, that is, a finite set of forbidden minors.

Some examples of finite obstruction sets were already known for specific classes of graphs before the Robertson–Seymour theorem was proved. For example, the obstruction for the set of all forests is the loop graph (or, if one restricts to simple graphs, the cycle with three vertices). This means that a graph is a forest if and only if none of its minors is the loop (or, the cycle with three vertices, respectively). The sole obstruction for the set of paths is the tree with four vertices, one of which has degree 3. In these cases, the obstruction set contains a single element, but in general this is not the case. Wagner's theorem states that a graph is planar if and only if it has neither K₅ nor K_3,3 as a minor. In other words, the set {K₅, K_3,3} is an obstruction set for the set of all planar graphs, and in fact the unique minimal obstruction set. A similar theorem states that K₄ and K_2,3 are the forbidden minors for the set of outerplanar graphs.

The Robertson–Seymour theorem extends these results to arbitrary sets of graphs that are downward closed with respect to the minor ordering. It is however not a complete generalization because it does not provide the exact obstruction sets. For example, it tells us that the set of torus-embeddable graphs has a finite obstruction set, but it does not provide any such set. In fact, the set of forbidden minors for torus-embeddable graphs is not known (but it is necessarily huge, as it has been shown^[1] to have more than 16000 elements).

[edit] Consequences

The Robertson–Seymour theorem has an important consequence in computational complexity, due to their proof of the existence of a polynomial-time algorithm for each fixed graph G that checks whether a G is a minor of a given input graph. As a result, membership of a graph to a fixed downward closed set can be checked by running this algorithm for all elements of the obstruction set.

Formally, if S is a fixed downward closed set (for example, the set of all planar graphs), the Robertson–Seymour theorem states that a finite obstruction set O of this set exists. As a result, checking whether a graph G is planar can be done iterating the check of whether H is a minor of G for all graphs H in this obstruction set. Since S is fixed, its finite obstruction set is fixed, and the graphs in it are fixed as well — that is, O is the same for every possible input graph. Since an algorithm for checking whether H is a minor of G is cubic (O(n³)) in the size of G, checking membership of G to S is cubic as well, the size of the obstruction set and of its graphs being regarded as a constant. In specific cases, checking whether a graph is in a set can be done more efficiently: for example, checking whether a graph is planar can be done in linear time.

The Robertson–Seymour theorem states that every downward closed set of graphs has a finite obstruction set; as a result, the above algorithm can be used for establishing whether a graph is in such a set. However, this method requires a specific finite obstruction set to work, and the theorem does not provide one. The theorem proves that such a finite obstruction set exists, and therefore the problem is polynomial because of the above algorithm. However, the algorithm can be used in practice only if such a finite obstruction set is provided. As a result, the theorem proves that the problem can be solved in polynomial time, but does not provide a concrete polynomial-time algorithm for solving it. Such proofs of polynomiality are non-constructive: they prove polynomiality of problems without providing a polynomial-time algorithm.

That the theorem shows the existence of a finite obstruction set without providing one may be counterintutive, because the theorems proving the existence of an object are typically proved by building such an object — they are constructive proofs. The Robertson–Seymour theorem is non-constructive: its proof is a reductio ad absurdum of the non-existence of a finite obstruction sets. In other words, the proof assumes that there exists a downward closed set whose obstruction sets are all infinite, and derives contradiction. That finite obstruction sets exist is proved by showing that their non-existence is contradictory. As a result, the finite obstruction set a finite downward closed set has cannot be distilled from the proof of the Robertson–Seymour theorem.

[edit] Fixed-parameter tractability

The Robertson–Seymour theorem is also especially relevant to the parameterized complexity of problems. Indeed, several graph problems can be characterized by downward closed sets only for a fixed value of a parameter. For example, the set of graphs that have genus equal to a fixed k is downward closed. As a result, for every fixed number k, the Robertson-Seymour theorem proves that establishing whether a graph has genus k can be done in polynomial time. However, this holds only if k is fixed, that is, it is not part of the input; it does not prove the same for the problem of establishing whether G has genus k given both G and k as input. Moreover, as the obstruction set is not necessarily known, the result is still non-constructive ; for instance, it has been shown that for k=1 (graphs which can be drawn on a torus), the obstruction set has more than 16000 elements, but it could well even be much larger...

[edit] Finite form of the graph minor theorem

Friedman, Robertson and Seymour [1987] showed that the following theorem exhibits the independence phenomenon by being unprovable in various formal systems that are much stronger than Peano arithmetic, yet being provable in systems much weaker than ZFC:

Theorem: For every positive integer n, there is an integer m so large that if G₁, ..., G_m is a sequence of finite undirected graphs,

where each G_i has size at most n+i, then G_j ≤ G_k for some j < k.

(Here, the size of a graph is the total number of its nodes and edges, and ≤ denotes the minor ordering.)

[edit] See also

• Forbidden graph characterization

[edit] References

• Lovasz, Laszlo (2005). "Graph Minor Theory". Bulletin of the American Mathematical Society (New Series) 43 (1): 75–86. doi:10.1090/S0273-0979-05-01088-8. http://www.ams.org/bull/2006-43-01/S0273-0979-05-01088-8/. 
• Robertson, Neil; P.D. Seymour (1983). "Graph Minors. I. Excluding a forest". Journal of Combinatorial Theory, Series B 35 (1): 39–61. doi:10.1016/0095-8956(83)90079-5. 
• Robertson, Neil; P.D. Seymour (2004). "Graph Minors. XX. Wagner's conjecture". Journal of Combinatorial Theory, Series B 92 (2): 325–357. doi:10.1016/j.jctb.2004.08.001. 
• Downey, Rod; M. Fellows (1999). Parameterized complexity. Springer. http://www.springer.com/sgw/cda/frontpage/0,11855,5-0-22-1519914-0,00.html?referer=www.springer.de%2Fcgi-bin%2Fsearch_book.pl%3Fisbn%3D0-387-94883-X.  ISBN 0-387-94883-X
• Bienstock, Daniel; Michael A. Langston (1995). "Algorithmic Implications of the Graph Minor Theorem". Handbooks in Operations Research and Management Science. Volume 7: Network Models. pp. 481–502. doi:10.1016/S0927-0507(05)80125-2. http://www.cs.utk.edu/~langston/courses/cs594-fall2003/BL.pdf. 
• Reinhard, Diestel (2005). "Minors Trees and WQO". Graph Theory (Electronic Edition 2005 ed.). Springer. pp. 326–367. http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/. 

• Friedman, Harvey, Robertson, Neil, and Seymour, P. D., "The Metamathematics of the Graph Minor Theorem", Logic and Combinatorics, ed. S. Simpson, AMS Contemporary Mathematics Series, vol. 65, 1987, 229-261.

• Friedman, Harvey (1988), "The Incompleteness Phenomena", Proceedings of the AMS Centennial Celebration, August 8-12, 1988, AMS Centennial Publications, Volume II, Mathematics into the Twenty-first Century, 1992, pp. 49-84.

[edit] External links

• Robertson-Seymour theorem at mathworld