Robertson–Seymour theorem
351769
220592153
2008-06-20T16:35:00Z
DOI bot
6652755
Citation maintenance. You can [[WP:DOI|use this bot]] yourself! Please [[User:DOI_bot/bugs|report any bugs]].
In [[graph theory]], the '''Robertson–Seymour theorem''' states that the [[Minor (graph theory)|minor ordering]] on the finite undirected graphs is a [[well-quasi-ordering]]. This statement can be reformulated as a statement about the finite representability of certain sets of graphs. In particular, every (possibly infinite) set of graphs that is downwardly closed according to the minor ordering is represented by a finite set of graphs called its obstruction set, where a graph is in the set if and only if none of its minors is in the obstruction set.
The statement is a generalisation of a theorem by the German mathematician [[Klaus Wagner (mathematician)|Klaus Wagner]] (1910–2000), and was called '''Wagner's conjecture''' until it was proved by [[Neil Robertson (mathematician)|Neil Robertson]] and [[Paul Seymour (mathematician)|Paul D. Seymour]], who published its proof in a series of twenty papers spanning over 500 pages from 1983 to 2004. A weaker result for [[tree (graph theory)|trees]] is implied by [[Kruskal's tree theorem]], which was proved in 1960.
==Statement==
The concepts involved in the statement of the theorem are:
[[Image:Forbidden-minors-1.svg|thumb|200px|A set that is closed downward: if ''G'' is in ''S'', all its minors, such as ''H'', are in ''S'' as well.]]
* A graph ''H'' is a '''[[minor (graph theory)|minor]]''' of a graph ''G'' if ''H'' is [[isomorphic]] to a graph obtained from ''G'' by [[edge contraction|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'';
* 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'', it holds ''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 [[forest (graph theory)|forest]]s
*The set of all [[planar graph]]s
*The set of all [[outerplanar graph]]s
*The set of all graphs that can be embedded without edge intersections in a [[torus]]
*the set of all graphs that can be embedded without edge intersections in a fixed arbitrary surface ''S''
*the set of all graphs that are [[knot (mathematics)|knotlessly]] embeddable in Euclidean 3-space
*the set of all graphs that are [[link (knot theory)|linklessly]] embeddable in Euclidean 3-space
[[Image:Forbidden-minors-2.svg|thumb|200px|An obstruction set: the elements not in the set are those greater than 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''': 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, an obstruction set for the set of all forests is the set containing only the cycle with three vertices. This means that a graph is a forest if and only if none of its minors is the cycle with three vertices. An obstruction set for the set of paths is the set containing only 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''<sub>5</sub> nor ''K''<sub>3,3</sub> as a minor. In other words, it states that the set {''K''<sub>5</sub>, ''K''<sub>3,3</sub>} is an obstruction set for the set of all planar graphs. A similar theorem states that ''K''<sub>4</sub> and ''K''<sub>2,3</sub> are a set of forbidden minors for the set of outerplanar graphs.
The Robertson–Seymour theorem in a way generalizes these results to arbitrary sets of graphs that are downward closed with respect to the minor ordering. It is however not exactly a generalization of the above results in that it does not provide the finite obstruction sets. For example, it tells that the set of torus-embeddable graphs has a finite obstruction set, but does not provide one such finite obstruction set. In fact, no finite obstruction set for the set of torus-embeddable graphs is known (but it is necessarily huge, as it has been shown<ref>J. Chambers, Hunting for torus obstructions, M.Sc. Thesis, Department of
Computer Science, University of Victoria, 2002.</ref> to have more than 16000 elements).
==Consequences==
The Robertson–Seymour theorem has an important consequence on computational complexity, due to the existence of a [[P (complexity)|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 ([[Big-O notation|O]](''n''<sup>3</sup>)) 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 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.
===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 (mathematics)#Graph theory|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...
==See also==
*[[Forbidden graph characterization]]
==References==
{{reflist}}
*{{citation|journal=BULLETIN (New Series) OF THE AMERICAN MATHEMATICAL SOCIETY
|volume= 43|issue= 1|pages= 75–86
|title= Graph Minor Theory
|first= LASZLO |last=LOVASZ
|url=http://www.ams.org/bull/2006-43-01/S0273-0979-05-01088-8/
|doi= 10.1090/S0273-0979-05-01088-8
|year= 2005}}
*{{cite journal
| first=Neil
| last=Robertson
| coauthors=P.D. Seymour
| title=Graph Minors. I. Excluding a forest
| journal=Journal of Combinatorial Theory, Series B
| volume=35
| issue=1
| year=1983
| pages=39–61
| doi=10.1016/0095-8956(83)90079-5
}}
*{{cite journal
| first=Neil
| last=Robertson
| coauthors=P.D. Seymour
| title=Graph Minors. XX. Wagner's conjecture
| journal=Journal of Combinatorial Theory, Series B
| volume=92
| issue=2
| year=2004
| pages=325–357
| doi=10.1016/j.jctb.2004.08.001
}}
*{{cite book
| first=Rod
| last=Downey
| coauthors=M. Fellows
| title=Parameterized complexity
| publisher=Springer
| year=1999
| url=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
*{{cite book
| first=Daniel
| last=Bienstock
| coauthor=Michael A. Langston
| chapter=Algorithmic Implications of the Graph Minor Theorem
| title=Handbooks in Operations Research and Management Science. Volume 7: Network Models
| pages=481-502
| doi=10.1016/S0927-0507(05)80125-2
| url=http://www.cs.utk.edu/~langston/courses/cs594-fall2003/BL.pdf
| year=1995
}}
*{{cite book
| last = Reinhard
| first = Diestel
| title = Graph Theory
| url = http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/
| edition = Electronic Edition 2005
| year = 2005
| publisher = Springer
| pages = 326–367
| chapter = Minors Trees and WQO
}}
==External links==
*[http://mathworld.wolfram.com/Robertson-SeymourTheorem.html Robertson-Seymour theorem at mathworld]
[[Category:Graph theory]]
[[Category:Wellfoundedness]]
[[Category:Mathematical theorems]]