Prize-collecting Steiner problems on planar graphs

M. Bateni, C. Chekuri, A. Ene, M. T. Hajiaghayi, N. Korula, D. Marx

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

In this paper, we reduce Prize-Collecting Steiner TSP (PCTSP), Prize-Collecting Stroll (PCS), Prize-Collecting Steiner Tree (PCST), Prize-Collecting Steiner Forest (PCSF), and more generally Submodular Prize-Collecting Steiner Forest (SPCSF), on planar graphs (and also on bounded-genus graphs) to the corresponding problem on graphs of bounded treewidth. More precisely, for each of the mentioned problems, an a-approximation algorithm for the problem on graphs of bounded treewidth implies an (α + ε)- approximation algorithm for the problem on planar graphs (and also bounded-genus graphs), for any constant ε > 0. PCS, PCTSP. and PCST can be solved exactly on graphs of bounded treewidth and hence we obtain a PTAS for these problems on planar graphs and bounded-genus graphs. In contrast, we show that PCSF is APX-hard to approximate on series-parallel graphs, which are planar graphs of treewidth at most 2. Apart from ruling out a PTAS for PCSF on planar graphs and bounded treewidth graphs, this result is also interesting since it gives the first provable hardness separation between the approxiinability of a problem and its prize-collecting version. We also show that PCSF is APX-hard on Euclidean instances.

Original languageEnglish (US)
Title of host publicationProceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011
PublisherAssociation for Computing Machinery
Pages1028-1049
Number of pages22
ISBN (Print)9780898719932
DOIs
StatePublished - Jan 1 2011

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Prize-collecting Steiner problems on planar graphs'. Together they form a unique fingerprint.

Cite this