## 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.