Approximation Schemes for Steiner Forest on Planar Graphs and Graphs of Bounded Treewidth

Details Approximation Schemes for Steiner Forest on Planar Graphs and Graphs of Bounded Treewidth Approximation Schemes for Steiner Forest on Planar Graphs and Graphs of Bounded Treewidth

2009-11-26

arxiv.org/abs/0911.5143v1

Computer Science

Data Structures and Algorithms

Scientific paper

We give the first polynomial-time approximation scheme (PTAS) for the Steiner forest problem on planar graphs and, more generally, on graphs of bounded genus. As a first step, we show how to build a Steiner forest spanner for such graphs. The crux of the process is a clustering procedure called prize-collecting clustering that breaks down the input instance into separate subinstances which are easier to handle; moreover, the terminals in different subinstances are far from each other. Each subinstance has a relatively inexpensive Steiner tree connecting all its terminals, and the subinstances can be solved (almost) separately. Another building block is a PTAS for Steiner forest on graphs of bounded treewidth. Surprisingly, Steiner forest is NP-hard even on graphs of treewidth 3. Therefore, our PTAS for bounded treewidth graph needs a nontrivial combination of approximation arguments and dynamic programming on the tree decomposition. We further show that Steiner forest can be solved in polynomial time for series-parallel graphs (graphs of treewidth at most two) by a novel combination of dynamic programming and minimum cut computations, completing our thorough complexity study of Steiner forest in the range of bounded treewidth graphs, planar graphs, and bounded genus graphs.

Affiliated with

Also associated with

No associations

Rating

Approximation Schemes for Steiner Forest on Planar Graphs and Graphs of Bounded Treewidth 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 Approximation Schemes for Steiner Forest on Planar Graphs and Graphs of Bounded Treewidth, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Approximation Schemes for Steiner Forest on Planar Graphs and Graphs of Bounded Treewidth will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-117033