TY - GEN

T1 - Degree-3 treewidth sparsifiers

AU - Chekuri, Chandra

AU - Chuzhoy, Julia

N1 - Publisher Copyright:
Copyright © 2015 by the Society for Industrial and Applied Mathmatics.

PY - 2015

Y1 - 2015

N2 - 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{k4); 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.

AB - 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{k4); 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.

UR - http://www.scopus.com/inward/record.url?scp=84938279359&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84938279359&partnerID=8YFLogxK

U2 - 10.1137/1.9781611973730.19

DO - 10.1137/1.9781611973730.19

M3 - Conference contribution

AN - SCOPUS:84938279359

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 242

EP - 255

BT - Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015

PB - Association for Computing Machinery

T2 - 26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015

Y2 - 4 January 2015 through 6 January 2015

ER -