**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 *G*, there is a polynomial time algorithm for testing whether larger graphs have *G* as a minor. The running time of this algorithm can be expressed as a cubic polynomial in the size of the larger graph (although there is a constant factor in this polynomial that depends superpolynomially on the size of *G*). As a result, for every minor-closed family *F*, there is polynomial time algorithm for testing whether a graph belongs to *F*: simply check, for each of the forbidden minors for *F*, whether the given graph contains that forbidden minor.

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. 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.

Read more about this topic: Robertson–Seymour Theorem

### Famous quotes containing the words time and/or recognition:

“... there was one of two things I had a right to, liberty, or death; if I could not have one, I would take de oder; for no man should take me alive; I should fight for my liberty as long as my strength lasted, and when de *time* came for me to go, de Lord would let dem take me.”

—Harriet Tubman (c. 1820–1913)

“Work expands so as to fill the time available for its completion. General *recognition* of this fact is shown in the proverbial phrase “It is the busiest man who has time to spare.””

—C. Northcote Parkinson (1909–1993)