Polynomial Bounds for the Grid-Minor Theorem

by Chandra Chekuri and Julia Chuzhoy

Oded's comments

As usual, Julia's talk was a delight, as reflected in the clear abstract. She explained that the dichotomy between having small treewidth and large grid-minor allows to apply one of two begs of algorithmic techniques, which apply to each of these cases. This approach becomes more appealing as the quantitative relation gets tighter, and this work makes an exponential improvement, leaving only a polynomial gap towards the optimal.

The original abstract

One of the key results in Robertson and Seymour's seminal work on graph minors is the Grid-Minor Theorem (also known as the Excluded Grid Theorem). The theorem states that any graph of treewidth at least $k$ contains a grid minor of size $f(k)$ for some function $f$. This theorem has found many applications in graph theory and algorithms. The best current quantitative bound, due to recent work of Kawarabayashi and Kobayashi, and Leaf and Seymour, shows that $f(k)=\Omega(\sqrt{\log k/\log \log k})$, while the best known upper bound implies that $f(k) =O(\sqrt{k/\log k})$. In this talk we present 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 also describe an efficient algorithm to construct such a minor.

Back to list of Oded's choices.