Loading...
Please wait, while we are loading the content...
Similar Documents
Polynomial bounds for the grid-minor theorem (2014)
| Content Provider | CiteSeerX |
|---|---|
| Author | Chekuri, Chandra Chuzhoy, Julia |
| Description | 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(k) denote the largest value, such that every graph of treewidth k contains a grid minor of size f(k) × f(k). The best current quantitative bound, due to recent work of Kawarabayashi and Kobayashi [KK12], and Leaf and Seymour [LS12], shows that f(k) = Ω( log k / log log k). In contrast, the best known upper bound implies that f(k) = O( k / log k) [RST94]. In this paper we obtain the first polynomial relationship between treewidth and grid-minor size by showing that f(k) = Ω(kδ) for some fixed constant δ> 0, and describe an algorithm, whose running time is polynomial in V (G) and k, that finds such a grid-minor. |
| File Format | |
| Language | English |
| Publisher Date | 2014-01-01 |
| Publisher Institution | EXTENDED ABSTRACT IN PROC. OF ACM STOC |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
