TY - GEN

T1 - Large-treewidth graph decompositions and applications

AU - Chekuri, Chandra Sekhar

AU - Chuzhoy, Julia

PY - 2013/7/11

Y1 - 2013/7/11

N2 - 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.

AB - 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.

KW - Erdos-pósa theorems

KW - Fixed parameter tractability

KW - Graph decomposition

KW - Grid minor theorem

KW - Treewidth

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

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

U2 - 10.1145/2488608.2488645

DO - 10.1145/2488608.2488645

M3 - Conference contribution

AN - SCOPUS:84879835446

SN - 9781450320290

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 291

EP - 300

BT - STOC 2013 - Proceedings of the 2013 ACM Symposium on Theory of Computing

T2 - 45th Annual ACM Symposium on Theory of Computing, STOC 2013

Y2 - 1 June 2013 through 4 June 2013

ER -