We prove that any graph excluding a fixed minor can have its edges partitioned
into a desired number k of color classes such that contracting the
edges in any one color class results in a graph of treewidth linear
in k. This result is a natural finale to research in contraction
decomposition, generalizing previous such decompositions for planar and
bounded-genus graphs, and solving the main open problem in this area (posed at
SODA 2007). Our decomposition can be computed in polynomial time, resulting
in a general framework for approximation algorithms, particularly PTASs (with
k ≈ 1/ε), and fixed-parameter algorithms, for
problems closed under contractions in graphs excluding a fixed minor. For
example, our approximation framework gives the first PTAS for TSP in weighted
H-minor-free graphs, solving a decade-old open problem of Grohe; and
gives another fixed-parameter algorithm for k-cut in
H-minor-free graphs, which was an open problem of Downey et al. even
for planar graphs.
To obtain our contraction decompositions, we develop new graph structure
theory to realize virtual edges in the clique-sum decomposition by actual
paths in the graph, enabling the use of the powerful Robertson--Seymour Graph
Minor decomposition theorem in the context of edge contractions (without edge
deletions). This requires careful construction of paths to avoid blowup in
the number of required paths beyond 3. Along the way, we strengthen and
simplify contraction decompositions for bounded-genus graphs, so that the
partition is determined by a simple radial ball growth independent of handles,
starting from a set of vertices instead of just one, as long as this set is
tight in a certain sense. We show that this tightness property holds for a
constant number of approximately shortest paths in the surface, introducing
several new concepts such as dives and rainbows.