TY - GEN

T1 - Prize-collecting Steiner problems on planar graphs

AU - Bateni, M.

AU - Chekuri, C.

AU - Ene, A.

AU - Hajiaghayi, M. T.

AU - Korula, N.

AU - Marx, D.

PY - 2011/1/1

Y1 - 2011/1/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=79955707403&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=79955707403&partnerID=8YFLogxK

U2 - 10.1137/1.9781611973082.79

DO - 10.1137/1.9781611973082.79

M3 - Conference contribution

AN - SCOPUS:79955707403

SN - 9780898719932

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 1028

EP - 1049

BT - Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011

PB - Association for Computing Machinery

ER -