Prize-collecting Network Design on Planar Graphs

Details Prize-collecting Network Design on Planar Graphs Prize-collecting Network Design on Planar Graphs

2010-06-22

arxiv.org/abs/1006.4339v1

Computer Science

Data Structures and Algorithms

Scientific paper

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 more generally bounded-genus graphs) to the same problems on graphs of bounded treewidth. More precisely, we show any $\alpha$-approximation algorithm for these problems on graphs of bounded treewidth gives an $(\alpha + \epsilon)$-approximation algorithm for these problems on planar graphs (and more generally bounded-genus graphs), for any constant $\epsilon > 0$. Since PCS, PCTSP, and PCST can be solved exactly on graphs of bounded treewidth using dynamic programming, we obtain PTASs for these problems on planar graphs and bounded-genus graphs. In contrast, we show PCSF is APX-hard to approximate on series-parallel graphs, which are planar graphs of treewidth at most 2. This result is interesting on its own because it gives the first provable hardness separation between prize-collecting and non-prize-collecting (regular) versions of the problems: regular Steiner Forest is known to be polynomially solvable on series-parallel graphs and admits a PTAS on graphs of bounded treewidth. An analogous hardness result can be shown for Euclidian PCSF. This ends the common belief that prize-collecting variants should not add any new hardness to the problems.

Affiliated with

Also associated with

No associations

Rating

Prize-collecting Network Design on Planar Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Prize-collecting Network Design on Planar Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Prize-collecting Network Design on Planar Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-108616