Large-treewidth graph decompositions and applications

DOI10.1145/2488608.2488645MaRDI QIDQ5495799zbMATH OpenOpenAlexFDO

Authors Chandra Chekuri, Julia Chuzhoy

Publication date 7 August 2014

Published in Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1304.1577

zbMATH Keywords

Erdős-Pósa theoremsfixed parameter tractabilitygraph decompositiongrid minor theoremtreewidth

Mathematics Subject Classification ID

Trees (05C05) Graph designs and isomorphic decomposition (05C51) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

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 node-disjoint 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 $h{r}^{2}lek/polylog(k)$, or $h^{3}rlek/polylog(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-Posa-type results, and faster algorithms for a class of fixed-parameter tractable problems.

Recommendations

• Graphs excluding a fixed minor have grids as large as treewidth, with combinatorial and algorithmic applications through bidimensionality
• Polynomial bounds for the grid-minor theorem
• Polynomial bounds for the grid-minor theorem
• Tree-width and large grid minors in planar graphs
• Linearity of grid minors in treewidth with applications through bidimensionality

Cited in

(25)

• Polynomial expansion and sublinear separators
• Explicit linear kernels for packing problems
• An \(O(\log \mathrm{OPT})\)-approximation for covering and packing minor models of \(\theta _r\)
• Degree-constrained decompositions of graphs: Bounded treewidth and planarity
• A tight Erdős-Pósa function for long cycles
• Minors in graphs of large _r-girth
• Packing and covering immersion-expansions of planar sub-cubic graphs
• Recent techniques and results on the Erdős-Pósa property
• Routing in undirected graphs with constant congestion
• An edge variant of the Erdős-Pósa property
• Packing and covering immersion models of planar subcubic graphs
• Erdös-Pósa Property of Obstructions to Interval Graphs
• Large discrete parts of the E-tree
• Decomposing large graphs with small graphs of high density
• Frames, \(A\)-paths, and the Erdős-Pósa property
• Constant congestion routing of symmetric demands in planar directed graphs
• Constant congestion brambles in directed graphs
• Packing directed circuits quarter-integrally
• Packing cycles faster than Erdős-Pósa
• A tight Erdős-Pósa function for wheel minors
• Erdős–Pósa property of obstructions to interval graphs
• Induced subgraphs and path decompositions
• Tight bound for the Erdős-Pósa property of tree minors
• Packing directed cycles quarter- and half-integrally
• The all-or-nothing flow problem in directed graphs with symmetric demand pairs

This page was built for publication: Large-treewidth graph decompositions and applications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5495799)