Prize-collecting Steiner Problems on Planar Graphs
Lists
Only you see this
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.
BibTeX
@inproceedings{bateni2011prize,
author = {MohammadHossein Bateni and Chandra Chekuri and Alina Ene and Mohammad Taghi Hajiaghayi and Nitish Korula and Dániel Marx},
title = {{Prize-collecting Steiner Problems on Planar Graphs}},
booktitle = {SODA},
year = {2011},
doi = {10.1137/1.9781611973082.79},
}Loading related content...