Paper by Erik D. Demaine
- Erik D. Demaine, MohammadTaghi Hajiaghayi, and Bojan Mohar, “Approximation Algorithms via Contraction Decomposition”, in Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2007), New Orleans, Louisiana, January 7–9, 2007, pages 278–287.
We prove that the edges of every graph of bounded (Euler)
genus can be partitioned into any prescribed
number k of pieces such that contracting any piece
results in a graph of bounded treewidth
(where the bound depends on k).
This decomposition result parallels an analogous, simpler result for
edge deletions instead of contractions, obtained in
[Bak94, Epp00, DDO+04, DHK05],
and it generalizes a similar result for “compression”
(a variant of contraction) in planar graphs [Kle05].
Our decomposition result is a powerful tool for obtaining PTASs for
contraction-closed problems (whose optimal solution only improves under
contraction), a much more general class than minor-closed problems.
We prove that any contraction-closed problem satisfying just a few simple
conditions has a PTAS in bounded-genus graphs.
In particular, our framework yields PTASs for the weighted
Traveling Salesman Problem and for minimum-weight c-edge-connected
submultigraph on bounded-genus graphs, improving and generalizing
previous algorithms of [GKP95, AGK+98, Kle05, Gri00, CGSZ04, BCGZ05].
We also highlight the only main difficulty in extending our results to
general H-minor-free graphs.
- The paper is available in PostScript (507k), gzipped PostScript (212k), and PDF (264k).
- See information on file formats.
- [Google Scholar search]
- Related papers:
- ContractionTSP_Combinatorica (Approximation Algorithms via Contraction Decomposition)
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated November 6, 2023 by