Editing Robertson–Seymour theorem (section)

==Polynomial time recognition==
The Robertson–Seymour theorem has an important consequence in computational complexity, due to the proof by Robertson and Seymour that, for each fixed graph <math>H</math>, there is a [[polynomial time]] algorithm for testing whether a graph has <math>H</math> as a minor. 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 <math>H</math>. The running time has been improved to quadratic by Kawarabayashi, Kobayashi, and Reed.<ref>{{harvtxt|Kawarabayashi|Kobayashi|Reed|2012}}</ref> As a result, for every minor-closed family <math>\mathcal{F}</math>, there is polynomial time algorithm for testing whether a graph belongs to <math>\mathcal{F}</math>: check whether the given graph contains <math>H</math> for each forbidden minor <math>H</math> in the obstruction set of <math>\mathcal{F}</math>.<ref>{{harvtxt|Robertson|Seymour|1995}}; {{harvtxt|Bienstock|Langston|1995}}, Theorem 2.1.4 and Corollary 2.1.5; {{harvtxt|Lovász|2005}}, Theorem 11, p. 83.</ref>

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 an explicit polynomial-time algorithm.<ref>{{harvtxt|Fellows|Langston|1988}}; {{harvtxt|Bienstock|Langston|1995}}, Section 6.</ref> In many specific cases, checking whether a graph is in a given minor-closed family can be done more efficiently: for example, checking whether a graph is planar can be done in linear time.