# Polynomial Bounds for the Grid-Minor Theorem

arXiv: https://arxiv.org/abs/1305.6577 · HTML: https://mlsanity.com/paper/1305.6577/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 May 2013.

## Built on by (most cited first, 1 of 1)

- [On the Power of Preconditioning in Sparse Linear Regression](https://mlsanity.com/paper/2106.09207/) (2021)

## Abstract (arXiv)

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)=Omega(√log k/log log k). In contrast, the best known upper bound implies that f(k) = O(√k/log k). In this paper we obtain the first polynomial relationship between treewidth and grid minor size by showing that f(k)=Omega(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.