TY - GEN

T1 - Polynomial bounds for the Grid-Minor Theorem

AU - Chekuri, Chandra

AU - Chuzhoy, Julia

PY - 2014

Y1 - 2014

N2 - One of the key results in Robertson and Seymour's seminal work on graph minors is the Grid-Minor Theorem (also called the Excluded Grid Theorem). The theorem states that for every fixed-size grid H, every graph whose treewidth is large enough, contains H as a minor. This theorem has found many applications in graph theory and algorithms. Let f(κ) denote the largest value, such that every graph of treewidth κ contains a grid minor of size f(κ) × f(κ). The best current quantitative bound, due to recent work of Kawarabayashi and Kobayashi [15], and Leaf and Seymour [18], shows that f(κ) = Ω(√ log κ/ log log κ). In contrast, the best known upper bound implies that f(κ) = O(√ κ/ log κ) [22]. In this paper we obtain the first polynomial relationship between treewidth and grid-minor size by showing that f(κ) = Ω(k δ) for some fixed constant δ > 0, and describe an algorithm, whose running time is polynomial in |V (G)| and κ, that finds a model of such a grid-minor in G.

AB - One of the key results in Robertson and Seymour's seminal work on graph minors is the Grid-Minor Theorem (also called the Excluded Grid Theorem). The theorem states that for every fixed-size grid H, every graph whose treewidth is large enough, contains H as a minor. This theorem has found many applications in graph theory and algorithms. Let f(κ) denote the largest value, such that every graph of treewidth κ contains a grid minor of size f(κ) × f(κ). The best current quantitative bound, due to recent work of Kawarabayashi and Kobayashi [15], and Leaf and Seymour [18], shows that f(κ) = Ω(√ log κ/ log log κ). In contrast, the best known upper bound implies that f(κ) = O(√ κ/ log κ) [22]. In this paper we obtain the first polynomial relationship between treewidth and grid-minor size by showing that f(κ) = Ω(k δ) for some fixed constant δ > 0, and describe an algorithm, whose running time is polynomial in |V (G)| and κ, that finds a model of such a grid-minor in G.

KW - Grid minor theorem

KW - Treewidth

UR - http://www.scopus.com/inward/record.url?scp=84904341286&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84904341286&partnerID=8YFLogxK

U2 - 10.1145/2591796.2591813

DO - 10.1145/2591796.2591813

M3 - Conference contribution

AN - SCOPUS:84904341286

SN - 9781450327107

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 60

EP - 69

BT - STOC 2014 - Proceedings of the 2014 ACM Symposium on Theory of Computing

PB - Association for Computing Machinery

T2 - 4th Annual ACM Symposium on Theory of Computing, STOC 2014

Y2 - 31 May 2014 through 3 June 2014

ER -