Polynomial Bounds for the Grid-Minor Theorem
Polynomial Bounds for the Grid-Minor Theorem
复制标题
网格小定理的多项式界
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Julia Chuzhoy
中科院分区：
文献类型：
--
作者：
C. Chekuri;Julia Chuzhoy
罗伯逊和西摩关于图子式的开创性工作的关键结果之一是网格子式定理（也称为排除网格定理）。该定理指出，对于每个网格H，每个树宽相对于|V（高）|包含H作为一个子元素。这个定理在图论和算法中有许多应用。设f（k）表示使得每个树宽为k的图都包含大小为（f（k）× f（k））的网格子式的最大值。由于Kawarabayashi和小林以及Leaf和Seymour最近的工作，以前最好的定量界表明f（k）=Ω（log k/log log k）。而最好的上界则意味着f（k）= O（k/log k）。本文通过证明f（k）= Ω（kδ）（δ > 0）得到了树宽与网格子尺寸之间的第一多项式关系，并描述了一个随机算法，其运行时间是多项式的|V（G）|和k，以高概率在G中找到这样的网格子的模型。
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 H, every graph whose treewidth is large enough relative to |V(H)| 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 previous quantitative bound, due to recent work of Kawarabayashi and Kobayashi, and Leaf and Seymour, shows that f(k)=Ω(√log k/log log k). In contrast, the best known upper bound implies that f(k) = O(√k/log k). In this article, 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 a randomized algorithm, whose running time is polynomial in |V(G)| and k, that with high probability finds a model of such a grid minor in G.