Abstract
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.
- Agrawal, A., Klein, P., and Ravi, R. 1995. When trees collide: An approximation algorithm for the generalized Steiner problem on networks. SIAM J. Comput. 24, 3, 440--456. Google ScholarDigital Library
- Agrawal, A., Klein, P. N., and Ravi, R. 1991. When trees collide: An approximation algorithm for the generalized Steiner problem on networks. In Proceedings of the 23rd Annual ACM Symposium on Theory of Computing (STOC). ACM, New York, 134--144. Google ScholarDigital Library
- Archer, A., Bateni, M., Hajiaghayi, M., and Karloff, H. 2009. Improved approximation algorithms for prize-collecting Steiner tree and TSP. In Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society, Los Alamitos, CA. Google ScholarDigital Library
- Arora, S. 1996. Polynomial time approximation schemes for Euclidean TSP and other geometric problems. In Proceedings of the 37th Annual Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society Press, Los Alamitos, CA. Google ScholarDigital Library
- Arora, S. 1998. Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. J. ACM 45, 5, 753--782. Google ScholarDigital Library
- Baker, B. S. 1994. Approximation algorithms for np-complete problems on planar graphs. J. ACM 41, 1, 153--180. Google ScholarDigital Library
- Bateni, M., Chekuri, C., Ene, A., Hajiaghayi, M., Korula, N., and Marx, D. 2011. Prize-collecting Steiner problems on planar graphs. In Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, Philadelphia, PA, 1028--1049. Google ScholarDigital Library
- Bateni, M., Hajiaghayi, M., Klein, P. N., and Mathieu, C. 2012. A polynomial-time approximation scheme for planar multiway cut. In Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Google ScholarDigital Library
- Berman, P. and Ramaiyer, V. 1992. Improved approximations for the Steiner tree problem. In Proceedings of the 3rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, Philadelphia, PA, 325--334. Google ScholarDigital Library
- Bern, M. and Plassmann, P. 1989. The Steiner problem with edge lengths 1 and 2. Inf. Proc. Lett. 32, 171--176. Google ScholarDigital Library
- Bodlaender, H. L. 1998. A partial k-arboretum of graphs with bounded treewidth. Theoret. Comput. Sci. 209, 1-2, 1--45. Google ScholarDigital Library
- Borradaile, G., Klein, P. N., and Mathieu, C. 2008. A polynomial-time approximation scheme for Euclidean Steiner forest. In Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society Press, Los Alamitos, CA, 115--124. Google ScholarDigital Library
- Borradaile, G., Demaine, E. D., and Tazari, S. 2009a. Polynomial-time approximation schemes for subset-connectivity problems in bounded genus graphs. In Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science (STACS). Springer, Berlin, 171--182.Google Scholar
- Borradaile, G., Klein, P. N., and Mathieu, C. 2009b. An O(n log n) approximation scheme for Steiner tree in planar graphs. ACM Trans. Algor. 5, 3. Google ScholarDigital Library
- Borradaile, G., Mathieu, C., and Klein, P. N. 2007. A polynomial-time approximation scheme for Steiner tree in planar graphs. In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, Philadelphia, PA, 1285--1294. Google ScholarDigital Library
- Byrka, J., Grandoni, F., Rothvoss, T., and Sanità, L. 2010. An improved LP-based approximation for Steiner tree. In Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC). ACM, New York, 583--592. Google ScholarDigital Library
- Cabello, S. and Chambers, E. W. 2007. Multiple source shortest paths in a genus g graph. In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, Philadelphia, PA, 89--97. Google ScholarDigital Library
- Cabello, S. and Mohar, B. 2005. Finding shortest non-separating and non-contractible cycles for topologically embedded graphs. In Proceedings of the 13th Annual European Symposium of Algorithms (ESA). Springer, Berlin, 131--142. Google ScholarDigital Library
- Demaine, E. D., Hajiaghayi, M., and Mohar, B. 2007. Approximation algorithms via contraction decomposition. In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, Philadelphia, PA, 278--287. Google ScholarDigital Library
- Erickson, R. E., Monma, C. L., and Veinott, A. F. 1987. Send-and-split method for minimum-concave-cost network flows. Math. Oper. Res. 12, 634--664. Google ScholarDigital Library
- Garey, M. R. and Johnson, D. S. 1977. The rectilinear Steiner tree problem is NP-complete. SIAM J. Appl. Math. 32, 4, 826--834.Google ScholarDigital Library
- Gassner, E. 2010. The Steiner forest problem revisited. J. Disc. Algor. 8, 2, 163. Google ScholarDigital Library
- Goemans, M. X. and Williamson, D. P. 1995. A general approximation technique for constrained forest problems. SIAM J. Comput. 24, 2, 296--317. Google ScholarDigital Library
- Hougardy, S. and Prömel, H. J. 1999. A 1.598 approximation algorithm for the Steiner problem in graphs. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, Philadelphia, PA, 448--453. Google ScholarDigital Library
- Karp, R. M. 1975. On the computational complexity of combinatorial problems. Networks 5, 45--68.Google ScholarDigital Library
- Karpinski, M. and Zelikovsky, A. 1997. New approximation algorithms for the Steiner tree problems. J. Combinat. Optimi. 1, 1, 47--65.Google ScholarCross Ref
- Klein, P. N. 2008. A linear-time approximation scheme for TSP in undirected planar graphs with edge-weights. SIAM J. Comput. 37, 6, 1926--1952. Google ScholarDigital Library
- Marx, D. 2005. NP-completeness of list coloring and precoloring extension on the edges of planar graphs. J. Graph Theory 49, 4, 313--324. Google ScholarDigital Library
- Marx, D. 2007. Precoloring extension on chordal graphs. In Graph Theory in Paris. Proceedings of a Conference in Memory of Claude Berge, Trends in Mathematics. Birkhäuser, Basel, Switzerland, 255--270.Google Scholar
- Marx, D. 2009. Complexity results for minimum sum edge coloring. Disc. Appl. Math. 157, 5, 1034--1045. Google ScholarDigital Library
- Mitchell, J. S. B. 1999. Guillotine subdivisions approximate polygonal subdivisions: A simple polynomial-time approximation scheme for geometric TSP, k-MST, and related problems. SIAM J. Comput. 28, 4, 1298--1309. Google ScholarDigital Library
- Mohar, B. and Thomassen, C. 2001. Graphs on Surfaces. Johns Hopkins University Press, Baltimore, MD.Google Scholar
- Prömel, H. J. and Steger, A. 1997. RNC-approximation algorithms for the Steiner problem. In Proceedings of the 14th Annual Symposium on Theoretical Aspects of Computer Science (STACS). Springer, Berlin, 559--570. Google ScholarDigital Library
- Richey, M. B. and Parker, R. G. 1986. On multiple Steiner subgraph problems. Networks 16, 4, 423--438.Google ScholarCross Ref
- Robertson, N. and Seymour, P. D. 1986. Graph minors. II. algorithmic aspects of tree-width. J. Algor. 7, 3, 309--322.Google ScholarCross Ref
- Robertson, N. and Seymour, P. D. 1994. Graph minors. XI. circuits on a surface. J. Combinatorial Theory, Series B 60, 1, 72--106. Google ScholarDigital Library
- Robins, G. and Zelikovsky, A. 2005. Tighter bounds for graph Steiner tree approximation. SIAM J. Discr. Math. 19, 1, 122--134. Google ScholarDigital Library
- Schaefer, T. J. 1978. The complexity of satisfiability problems. In Proceedings of the 10th Annual ACM Symposium on Theory of Computing (STOC). ACM, New York, 216--226. Google ScholarDigital Library
- Thimm, M. 2003. On the approximability of the Steiner tree problem. Theor. Comput. Sci. 295, 1-3, 387--402. Google ScholarDigital Library
- Zelikovsky, A. 1992. An 11/6-approximation for the Steiner problem on graphs. In Proceedings of the 4th Czechoslovakian Symposium on Combinatorics, Graphs, and Complexity (1990) in Annals of Discrete Mathematics. Vol. 51. Elsevier, 351--354.Google ScholarCross Ref
- Zelikovsky, A. 1993. An 11/6-approximation algorithm for the network Steiner problem. Algorithmica 9, 5, 463--470.Google ScholarCross Ref
- Zelikovsky, A. 1996. Better approximation bounds for the network and Euclidean Steiner tree problems. Tech. rep., University of Virginia, Charlottesville, VA. Google ScholarDigital Library
- Zhou, X. and Nishizeki, T. 1998. The edge-disjoint paths problem is NP-complete for partial k-trees. In Algorithms and Computation (Taejon, 1998). Springer, Berlin, 417--426. Google ScholarDigital Library
Index Terms
- Approximation Schemes for Steiner Forest on Planar Graphs and Graphs of Bounded Treewidth
Recommendations
Approximation schemes for steiner forest on planar graphs and graphs of bounded treewidth
STOC '10: Proceedings of the forty-second ACM symposium on Theory of computingWe 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 ...
On r-acyclic edge colorings of planar graphs
A proper edge coloring of G is r-acyclic if every cycle C contained in G is colored with at least min{|C|,r} colors. The r-acyclic chromatic index of a graph, denoted by a"r^'(G), is the minimum number of colors required to produce an r-acyclic edge ...
The Steiner Forest Problem revisited
The Steiner Forest Problem (SFP for short) is a natural generalization of the classical Steiner Tree Problem. Instead of only one terminal net there is given a set of terminal nets that have to be connected by choosing edges at minimum cost. Richey and ...
Comments