Paper by Erik D. Demaine

Reference:
Erik D. Demaine, MohammadTaghi Hajiaghayi, and Bojan Mohar, “Approximation Algorithms via Contraction Decomposition”, Combinatorica, volume 30, number 5, 2010, pages 533–552.

Abstract:
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.

Copyright:
Copyright held by the authors.

Length:
The paper is 15 pages.

Availability:
The paper is available in PostScript (464k), gzipped PostScript (193k), and PDF (239k).
See information on file formats.
[Google Scholar search]

Related papers:
ContractionTSP_SODA2007 (Approximation Algorithms via Contraction Decomposition)


See also other papers by Erik Demaine.
These pages are generated automagically from a BibTeX file.
Last updated March 12, 2024 by Erik Demaine.