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

作者：Bateni Mohammadhossein^*; Hajiaghayi Mohammadtaghi; Marx Daniel

来源：Journal of the ACM, 2011, 58(5): 21.

DOI：10.1145/2027216.2027219

• Algorithms
• Design
• Performance
• Theory
• Approximation algorithm
• bounded-treewidth
• dynamic programming
• network design
• planar graph
• PTAS
• series-parallel graph
• Steiner forest

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

• 出版日期2011-10