### Polynomial Bounds for the Grid-Minor TheoremPolynomial Bounds for the Grid-Minor Theorem

Access Restriction
Subscribed

 Author Chekuri, Chandra ♦ Chuzhoy, Julia Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2016 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Excluded grid theorem ♦ Graph minor theory Abstract 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 grid $\textit{H},$ every graph whose treewidth is large enough relative to $|\textit{V}(\textit{H})|$ contains $\textit{H}$ as a minor. This theorem has found many applications in graph theory and algorithms. Let $\textit{f}(\textit{k})$ denote the largest value such that every graph of treewidth $\textit{k}$ contains a grid minor of size $(\textit{f}(\textit{k})$ × $\textit{f}(\textit{k})).$ The best previous quantitative bound, due to recent work of Kawarabayashi and Kobayashi, and Leaf and Seymour, shows that $\textit{f}(\textit{k})=Ω(&sqrt;log$ $\textit{k}/log$ log $\textit{k}).$ In contrast, the best known upper bound implies that $\textit{f}(\textit{k})$ = $\textit{O}(&sqrt;\textit{k}/log$ $\textit{k}).$ In this article, we obtain the first polynomial relationship between treewidth and grid minor size by showing that $\textit{f}(\textit{k})$ = $Ω(k^{Δ})$ for some fixed constant Δ > 0, and describe a randomized algorithm, whose running time is polynomial in $|\textit{V}(\textit{G})|$ and $\textit{k},$ that with high probability finds a model of such a grid minor in $\textit{G}.$ Description Author Affiliation: University of Illinois, Urbana-Champaign, Urbana, IL (Chekuri, Chandra); Toyota Technological Institute at Chicago, Chicago IL (Chuzhoy, Julia) ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2016-12-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 63 Issue Number 5 Page Count 65 Starting Page 1 Ending Page 65

#### Open content in new tab

Source: ACM Digital Library