Robertson–Seymour Theorem - Polynomial Time Recognition

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)