Polynomial Bounds for the Grid-Minor Theorem

被引:31
作者
Chekuri, Chandra [1 ]
Chuzhoy, Julia [2 ]
机构
[1] Univ Illinois, Dept Comp Sci, 1304 W Springfield Ave, Urbana, IL 61801 USA
[2] Toyota Technol Inst Chicago, Chicago, IL 60637 USA
来源
STOC'14: PROCEEDINGS OF THE 46TH ANNUAL 2014 ACM SYMPOSIUM ON THEORY OF COMPUTING | 2014年
关键词
Treewidth; grid minor theorem;
D O I
10.1145/2591796.2591813
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
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) x f (k). The best current quantitative bound, due to recent work of Kawarabayashi and Kobayashi [15], and Leaf and Seymour [18], shows that f (k) = Omega(root/log k/ log log k). In contrast, the best known upper bound implies that f (k) = O(root/k/log k) [22]. In this paper we obtain the first polynomial relationship between treewidth and grid-minor size by showing that f (k) = Omega(k(delta)) for some fixed constant delta > 0, and describe an algorithm, whose running time is polynomial in vertical bar V (G)vertical bar and k, that finds a model of such a grid-minor in G.
引用
收藏
页码:60 / 69
页数:10
相关论文
共 24 条
[1]   Expander Flows, Geometric Embeddings and Graph Partitioning [J].
Arora, Sanjeev ;
Rao, Satish ;
Vazirani, Umesh .
JOURNAL OF THE ACM, 2009, 56 (02)
[2]  
Chekuri C, 2013, STOC'13: PROCEEDINGS OF THE 2013 ACM SYMPOSIUM ON THEORY OF COMPUTING, P291
[3]   THE ALL-OR-NOTHING MULTICOMMODITY FLOW PROBLEM [J].
Chekuri, Chandra ;
Khanna, Sanjeev ;
Shepherd, F. Bruce .
SIAM JOURNAL ON COMPUTING, 2013, 42 (04) :1467-1493
[4]  
Chekuri Chandra, 2013, P ACM SIAM SODA
[5]  
Chekuri Chandra, 2013, CORR
[6]  
Chuzhoy J, 2012, STOC'12: PROCEEDINGS OF THE 2012 ACM SYMPOSIUM ON THEORY OF COMPUTING, P855
[7]  
Chuzhoy Julia, 2012, P IEEE FOCS
[8]   Reconstructing edge-disjoint paths [J].
Conforti, M ;
Hassin, R ;
Ravi, R .
OPERATIONS RESEARCH LETTERS, 2003, 31 (04) :273-276
[9]   Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs [J].
Demaine, ED ;
Fomin, FV ;
Hajiaghayi, M ;
Thilikos, DM .
JOURNAL OF THE ACM, 2005, 52 (06) :866-893
[10]   Linearity of grid minors in treewidth with applications through bidimensionality [J].
Demaine, Erik D. ;
Hajiachayi, Mohammadtaghi .
COMBINATORICA, 2008, 28 (01) :19-36