Access Restriction

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

   Open content in new tab
Source: ACM Digital Library