Robertson–Seymour theorem

The Robertson–Seymour theorem is named after mathematicians Neil Robertson and Paul D. Seymour, who proved it in a series of twenty papers spanning over 500 pages from 1983 to 2004.

The existence of forbidden minor characterizations for all minor-closed graph families is an equivalent way of stating the Robertson–Seymour theorem.

This algorithm's running time is cubic (in the size of the graph to check), though with a constant factor that depends superpolynomially on the size of the minor h. The running time has been improved to quadratic by Kawarabayashi, Kobayashi, and Reed.

[13] 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.

For instance, by this result, treewidth, branchwidth, and pathwidth, vertex cover, and the minimum genus of an embedding are all amenable to this approach, and for any fixed k there is a polynomial time algorithm for testing whether these invariants are at most k, in which the exponent in the running time of the algorithm does not depend on k. A problem with this property, that it can be solved in polynomial time for any fixed k with an exponent that does not depend on k, is known as fixed-parameter tractable.

However, this method does not directly provide a single fixed-parameter-tractable algorithm for computing the parameter value for a given graph with unknown k, because of the difficulty of determining the set of forbidden minors.

Additionally, the large constant factors involved in these results make them highly impractical.

Therefore, the development of explicit fixed-parameter algorithms for these problems, with improved dependence on k, has continued to be an important line of research.

Friedman, Robertson & 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: (Here, the size of a graph is the total number of its vertices and edges, and ≤ denotes the minor ordering.)