Catching Rats in H-minor-free Graphs

We show that every H-minor-free graph that also excludes a (k × k)-grid as a minor has treewidth/branchwidth bounded from above by a function f (t, k) that is linear in k and polynomial in t := |V (H)|. Such a result was proven originally by [Demaine & Hajiaghayi, Combinatorica, 2008], where f was indeed linear in k. However the dependency in t in this result was non-explicit (and huge). Later, [Kawarabayashi & Kobayashi, JCTB, 2020] showed that this bound can be estimated to be f (t, k) ∈ 2 O(t log t) • k. Wood recently asked whether f can be pushed further to be polynomial, while maintaining the linearity on k. We answer this in a particularly strong sense, by showing that the treewidth/branchwidth of G is in O(gk + t 2304 ), where g is the Euler genus of H. This directly yields f (t, k) = O(t 2 k + t 2304 ).

Our methods build on techniques for branchwidth and on new bounds and insights for the Graph Minor Structure Theorem (GMST) due to [Gorsky, Seweryn & Wiederrecht, 2025, arXiv:2504.02532]. In particular, we prove a variant of the GMST that ensures some helpful properties for the minor relation. We further employ our methods to provide approximation algorithms for the treewidth/branchwidth of H-minor-free graphs. In particular, for every ε > 0 and every t-vertex graph H with Euler genus g, we give a (g + ε)-approximation algorithm for the branchwidth of H-minor-free graphs running in 2 poly(t)/ε • poly(n)-time. Our algorithms explicitly return either an appropriate branch-decomposition or a grid-minor certifying a negative answer.