Robertson–Seymour theorem

From Wikipedia, the free encyclopedia

In graph theory, the Robertson–Seymour theorem states that the 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 (1910–2000), and was called Wagner's conjecture until it was proved by Neil Robertson and 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 trees is implied by Kruskal's tree theorem, which was proved in 1960.

Contents

[edit] Statement

The concepts involved in the statement of the theorem are:

A set that is closed downward: if G is in S, all its minors, such as H, are in S as well.
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 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;
  • 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 forests
  • The set of all planar graphs
  • The set of all outerplanar graphs
  • 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 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 a forbidden minor
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 K5 nor K3,3 as a minor. In other words, it states that the set {K5, K3,3} is an obstruction set for the set of all planar graphs. A similar theorem states that K4 and K2,3 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[1] to have more than 16000 elements).

[edit] Consequences

The Robertson–Seymour theorem has an important consequence on computational complexity, due to 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(n3)) 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.

[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] See also

[edit] References

  1. ^ J. Chambers, Hunting for torus obstructions, M.Sc. Thesis, Department of Computer Science, University of Victoria, 2002.

[edit] External links