Graph minors. II. Algorithmic aspects of tree-width
N Robertson, PD Seymour - Journal of algorithms, 1986 - Elsevier
We introduce an invariant of graphs called the tree-width, and use it to obtain a polynomially
bounded algorithm to test if a graph has a subgraph contractible to H, where H is any fixed
planar graph. We also nonconstructively prove the existence of a polynomial algorithm to
test if a graph has tree-width≤ w, for fixed w. Neither of these is a practical algorithm, as the
exponents of the polynomials are large. Both algorithms are derived from a polynomial
algorithm for the DISJOINT CONNECTING PATHS problem (with the number of paths fixed) …
bounded algorithm to test if a graph has a subgraph contractible to H, where H is any fixed
planar graph. We also nonconstructively prove the existence of a polynomial algorithm to
test if a graph has tree-width≤ w, for fixed w. Neither of these is a practical algorithm, as the
exponents of the polynomials are large. Both algorithms are derived from a polynomial
algorithm for the DISJOINT CONNECTING PATHS problem (with the number of paths fixed) …