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 BibTeX file.
Last updated July 23, 2024 by Erik Demaine.