Polynomial Bounds for the Graph Minor Structure Theorem

The Graph Minor Structure Theorem, originally proven by Robertson and Seymour [JCTB, 2003], asserts that there exist functions $f_1,f_2\text{\hspace{0.17em}⁣}:\mathbb{N}\to \mathbb{N}$ such that for every non-planar graph $H$ with $t:=\mathrm{\mid }V(H)\mathrm{\mid }$, every $H$-minor-free graph can be obtained via the clique-sum operation from graphs which embed into surfaces where $H$ does not embed after deleting at most $f_1(t)$ many vertices with up to at most $t^2-1$ many vortices'' which are of depth’’ at most $f_2(t)$. In the proof presented by Robertson and Seymour the functions $f_1$ and $f_2$ are non-constructive. Kawarabayashi, Thomas, and Wollan [arXiv, 2020] found a new proof showing that $f_1(t),f_2(t)\in 2^{\mathbf{p}\mathbf{o}\mathbf{l}\mathbf{y}(t)}$. While believing that this bound was the best their methods could achieve, Kawarabayashi, Thomas, and Wollan conjectured that $f_1$ and $f_2$ can be improved to be polynomials. In this paper we confirm their conjecture and prove that $f_1(t),f_2(t)\in \mathbf{O}(t^{2300})$. Our proofs are fully constructive and yield a polynomial-time algorithm that either finds $H$ as a minor in a graph $G$ or produces a clique-sum decomposition for $G$ as above.