skip to main content
research-article

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

Published:01 October 2011Publication History
Skip Abstract Section

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.

References

  1. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  2. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  3. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  4. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  5. Arora, S. 1998. Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. J. ACM 45, 5, 753--782. Google ScholarGoogle ScholarDigital LibraryDigital Library
  6. Baker, B. S. 1994. Approximation algorithms for np-complete problems on planar graphs. J. ACM 41, 1, 153--180. Google ScholarGoogle ScholarDigital LibraryDigital Library
  7. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  8. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  9. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  10. Bern, M. and Plassmann, P. 1989. The Steiner problem with edge lengths 1 and 2. Inf. Proc. Lett. 32, 171--176. Google ScholarGoogle ScholarDigital LibraryDigital Library
  11. Bodlaender, H. L. 1998. A partial k-arboretum of graphs with bounded treewidth. Theoret. Comput. Sci. 209, 1-2, 1--45. Google ScholarGoogle ScholarDigital LibraryDigital Library
  12. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  13. 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 ScholarGoogle Scholar
  14. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  15. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  16. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  17. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  18. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  19. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  20. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  21. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  22. Gassner, E. 2010. The Steiner forest problem revisited. J. Disc. Algor. 8, 2, 163. Google ScholarGoogle ScholarDigital LibraryDigital Library
  23. Goemans, M. X. and Williamson, D. P. 1995. A general approximation technique for constrained forest problems. SIAM J. Comput. 24, 2, 296--317. Google ScholarGoogle ScholarDigital LibraryDigital Library
  24. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  25. Karp, R. M. 1975. On the computational complexity of combinatorial problems. Networks 5, 45--68.Google ScholarGoogle ScholarDigital LibraryDigital Library
  26. Karpinski, M. and Zelikovsky, A. 1997. New approximation algorithms for the Steiner tree problems. J. Combinat. Optimi. 1, 1, 47--65.Google ScholarGoogle ScholarCross RefCross Ref
  27. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  28. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  29. 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 ScholarGoogle Scholar
  30. Marx, D. 2009. Complexity results for minimum sum edge coloring. Disc. Appl. Math. 157, 5, 1034--1045. Google ScholarGoogle ScholarDigital LibraryDigital Library
  31. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  32. Mohar, B. and Thomassen, C. 2001. Graphs on Surfaces. Johns Hopkins University Press, Baltimore, MD.Google ScholarGoogle Scholar
  33. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  34. Richey, M. B. and Parker, R. G. 1986. On multiple Steiner subgraph problems. Networks 16, 4, 423--438.Google ScholarGoogle ScholarCross RefCross Ref
  35. Robertson, N. and Seymour, P. D. 1986. Graph minors. II. algorithmic aspects of tree-width. J. Algor. 7, 3, 309--322.Google ScholarGoogle ScholarCross RefCross Ref
  36. Robertson, N. and Seymour, P. D. 1994. Graph minors. XI. circuits on a surface. J. Combinatorial Theory, Series B 60, 1, 72--106. Google ScholarGoogle ScholarDigital LibraryDigital Library
  37. Robins, G. and Zelikovsky, A. 2005. Tighter bounds for graph Steiner tree approximation. SIAM J. Discr. Math. 19, 1, 122--134. Google ScholarGoogle ScholarDigital LibraryDigital Library
  38. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  39. Thimm, M. 2003. On the approximability of the Steiner tree problem. Theor. Comput. Sci. 295, 1-3, 387--402. Google ScholarGoogle ScholarDigital LibraryDigital Library
  40. 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 ScholarGoogle ScholarCross RefCross Ref
  41. Zelikovsky, A. 1993. An 11/6-approximation algorithm for the network Steiner problem. Algorithmica 9, 5, 463--470.Google ScholarGoogle ScholarCross RefCross Ref
  42. Zelikovsky, A. 1996. Better approximation bounds for the network and Euclidean Steiner tree problems. Tech. rep., University of Virginia, Charlottesville, VA. Google ScholarGoogle ScholarDigital LibraryDigital Library
  43. 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 ScholarGoogle ScholarDigital LibraryDigital Library

Index Terms

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

          Recommendations

          Comments

          Login options

          Check if you have access through your login credentials or your institution to get full access on this article.

          Sign in

          Full Access

          • Published in

            cover image Journal of the ACM
            Journal of the ACM  Volume 58, Issue 5
            October 2011
            126 pages
            ISSN:0004-5411
            EISSN:1557-735X
            DOI:10.1145/2027216
            Issue’s Table of Contents

            Copyright © 2011 ACM

            Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

            Publisher

            Association for Computing Machinery

            New York, NY, United States

            Publication History

            • Published: 1 October 2011
            • Revised: 1 August 2011
            • Accepted: 1 August 2011
            • Received: 1 April 2010
            Published in jacm Volume 58, Issue 5

            Permissions

            Request permissions about this article.

            Request Permissions

            Check for updates

            Qualifiers

            • research-article
            • Research
            • Refereed

          PDF Format

          View or Download as a PDF file.

          PDF

          eReader

          View online with eReader.

          eReader