Large-treewidth graph decompositions and applications

Chandra Sekhar Chekuri, Julia Chuzhoy

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

Abstract

Treewidth is a graph parameter that plays a fundamental role in several structural and algorithmic results. We study the problem of decomposing a given graph G into nodedisjoint subgraphs, where each subgraph has sufficiently large treewidth. We prove two theorems on the tradeoff between the number of the desired subgraphs h, and the desired lower bound r on the treewidth of each subgraph. The theorems assert that, given a graph G with treewidth k, a decomposition with parameters h; r is feasible whenever hr2 ≤ k=poly log(k), or h3r ≤ k=poly log(k) holds. We then show a framework for using these theorems to bypass the well-known Grid-Minor Theorem of Robertson and Seymour in some applications. In particular, this leads to substantially improved parameters in some Erdos-Pósa-type results, and faster algorithms for some fixed-parameter tractable problems.

Original languageEnglish (US)
Title of host publicationSTOC 2013 - Proceedings of the 2013 ACM Symposium on Theory of Computing
Pages291-300
Number of pages10
DOIs
StatePublished - Jul 11 2013
Event45th Annual ACM Symposium on Theory of Computing, STOC 2013 - Palo Alto, CA, United States
Duration: Jun 1 2013Jun 4 2013

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Other

Other45th Annual ACM Symposium on Theory of Computing, STOC 2013
CountryUnited States
CityPalo Alto, CA
Period6/1/136/4/13

Keywords

  • Erdos-pósa theorems
  • Fixed parameter tractability
  • Graph decomposition
  • Grid minor theorem
  • Treewidth

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'Large-treewidth graph decompositions and applications'. Together they form a unique fingerprint.

Cite this