Polynomial bounds for the grid-minor theorem

Chandra Chekuri, Julia Chuzhoy

Research output: Contribution to journalArticlepeer-review

Abstract

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

Original languageEnglish (US)
Article number40
JournalJournal of the ACM
Volume63
Issue number5
DOIs
StatePublished - Dec 2016

Keywords

  • Excluded grid theorem
  • Graph minor theory

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • Information Systems
  • Hardware and Architecture
  • Artificial Intelligence

Fingerprint

Dive into the research topics of 'Polynomial bounds for the grid-minor theorem'. Together they form a unique fingerprint.

Cite this