Paper by Erik D. Demaine

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.

BibTeX

@InProceedings{ContractionTSP_SODA2007,
  AUTHOR        = {Erik D. Demaine and MohammadTaghi Hajiaghayi and
                   Bojan Mohar},
  TITLE         = {Approximation Algorithms via Contraction Decomposition},
  BOOKTITLE     = {Proceedings of the 18th Annual ACM-SIAM Symposium on
                   Discrete Algorithms (SODA 2007)},
  bookurl       = {http://www.siam.org/meetings/da07/},
  ADDRESS       = {New Orleans, Louisiana},
  MONTH         = {January 7--9},
  YEAR          = 2007,
  PAGES         = {278--287},

  papers        = {ContractionTSP_Combinatorica},
  dblp          = {https://dblp.org/rec/conf/soda/DemaineHM07},
  ee            = {https://dl.acm.org/doi/10.5555/1283383.1283413},
  comments      = {This paper is also available from <A HREF="https://dl.acm.org/doi/10.5555/1283383.1283413">ACM</A>.},
}

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.

Comments:

This paper is also available from ACM.

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)