**Reference**:- 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. **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. **Availability**:- 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.

Last updated September 18, 2020 by Erik Demaine.