Degree-3 treewidth sparsifiers

Chandra Chekuri, Julia Chuzhoy

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationProceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015
PublisherAssociation for Computing Machinery
Pages242-255
Number of pages14
EditionJanuary
ISBN (Electronic)9781611973747
DOIs
StatePublished - 2015
Event26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015 - San Diego, United States
Duration: Jan 4 2015Jan 6 2015

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
NumberJanuary
Volume2015-January

Other

Other26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015
Country/TerritoryUnited States
CitySan Diego
Period1/4/151/6/15

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Fingerprint

Dive into the research topics of 'Degree-3 treewidth sparsifiers'. Together they form a unique fingerprint.

Cite this