Graph minors. II. Algorithmic aspects of tree-width (1986)

---

Link: https://www.sciencedirect.com/science/article/abs/pii/0196677486900234

Abstract: 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 $\leq 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), for graphs of bounded tree-width.

---