Name
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 α-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 approximability of a problem and its prize-collecting version. We also show that PCSF is APX-hard on Euclidean instances. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.5555/2133036.2133115 | SODA |
Keywords | Field | DocType |
bounded treewidth,bounded treewidth graph,prize-collecting steiner forest,prize-collecting steiner tree,submodular prize-collecting steiner forest,planar graph,prize-collecting stroll,approximation algorithm,prize-collecting steiner problem,steiner tsp,bounded-genus graph,correspondence problem,randomized algorithms,distributed computing,steiner tree,leader election | Discrete mathematics,Indifference graph,Combinatorics,Tree-depth,Partial k-tree,Clique-sum,Chordal graph,Treewidth,Pathwidth,1-planar graph,Mathematics | Conference |
ISBN | Citations | PageRank |
978-1-61197-251-1 | 12 | 0.56 |
References | Authors | |
41 | 6 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| M. Bateni | 1 | 12 | 0.89 |
| Chandra Chekuri | 2 | 3493 | 293.51 |
| Alina Ene | 3 | 409 | 25.47 |
| MohammadTaghi Hajiaghayi | 4 | 3082 | 201.38 |
| N. Korula | 5 | 12 | 0.56 |
| Dániel Marx | 6 | 1952 | 113.07 |