← All papers
First page of A Polynomial-Time Sixth-Power Excluded Grid Theorem

A Polynomial-Time Sixth-Power Excluded Grid Theorem

Mohammad Hajiaghayi

cs.DS Nov 12, 2026 · v1
A companion Lean development verifies the algorithmic construction, its success-probability guarantee, and polynomial running-time composition, with published algorithms supplied as explicit interfaces.
We give a polynomial-time construction for a sixth-power excluded-grid theorem. Every graph whose treewidth is at least $g^6$ times a fixed polylogarithmic factor contains a $g\times g$ grid minor that our randomized algorithm finds with constant probability. The algorithm outputs an explicit minor model, and the exponent in its running time is independent of $g$. This improves the ninth-power existence bound of Chuzhoy and Tan \cite{CT21} and the $g^{98}$ threshold in the polynomial-time construction of Chekuri and Chuzhoy \cite{CC16}. Quantitative bounds relating treewidth to grid size are central to bidimensionality, developed by Demaine, Hajiaghayi, and collaborators \cite{DH05,DH08}. The main ingredient is an asymmetric local routing theorem that uses substantially fewer attachment paths than backbone paths. A balanced recursion preserves connectivity by charging deletions to the boundary of a fixed reference cluster. We construct the smaller attachment sets through a routing hierarchy: either it exposes an accessible well-linked boundary, or its quotient graphs contain the desired grid. These arguments implement cluster splitting using approximate cuts and flow computations. An explicit cut-matching construction and a constructive grid-extraction procedure complete the algorithm. We also give a general packing–covering hypothesis for trees meeting three prescribed terminal sets under which the exponent can be reduced below six. A companion Lean development verifies the new construction, its success guarantee, and the composition of its polynomial running time, using explicit interfaces for the published algorithms and standard finite-data operations.

The question is how large treewidth must be to force a g×g grid minor, and whether such a grid can be found in polynomial time. The best previous bounds were a ninth-power existence result (Chuzhoy–Tan) and a g^98 threshold for polynomial-time construction (Chekuri–Chuzhoy).

The main ingredient is an asymmetric local routing theorem that needs far fewer attachment paths than backbone paths. The smaller attachment sets come from a routing hierarchy built with minimum-cost flow, frontier sweeps in perfect unique linkages, and max-flow trimming against a fixed well-linked reference cluster. Cluster splitting uses approximate cuts and flow computations, and an explicit cut-matching construction plus grid extraction complete the algorithm. A companion Lean development verifies the construction, its success guarantee and its running-time composition.

Every graph with treewidth at least g^6 times a polylogarithmic factor contains a g×g grid minor. A randomized algorithm finds an explicit minor model with constant probability, and the exponent of its running time is independent of g. Under a packing–covering hypothesis for trees meeting three terminal sets, the exponent drops below six.