Degree-3 treewidth sparsifiers

We study treewidth sparsifiers. Informally, given a graph G of treewidth k, a treewidth sparsifier H is a minor of G, whose treewidth is close to k, \V(H)\ is small, and the maximum vertex degree in H is bounded. Treewidth sparsifiers of degree 3 are of particular interest, as routing on node-disjoint paths, and computing minors seems easier in sub-cubic graphs than in general graphs. In this paper we describe an algorithm that, given a graph G of treewidth k, computes a topological minor H of G such that (i) the treewidth of H is ω(κ/polylog(k)); (ii) \V(H)\ = 0{k⁴); and (iii) the maximum vertex degree in H is 3. The running time of the algorithm is polynomial in | V(G)| and k. Our result is in contrast to the known fact that unless NP C coNP/poly, treewidth does not admit polynomial-size kernels. One of our key technical tools, which is of independent interest, is a construction of a small minor that preserves node-disjoint routability between two pairs of vertex subsets. This is closely related to the open question of computing small good-quality vertex-cut sparsifiers that are also minors of the original graph.