MohammadHossein Bateni
MohammadTaghi Hajiaghayi
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.
- A. Agrawal, P. Klein, and R. Ravi. When trees collide: an approximation algorithm for the generalized Steiner problem on networks. SIAM J. Comput., 24(3):440--456, 1995. Google Scholar
Digital Library
- A. Agrawal, P. N. Klein, and R. Ravi. When trees collide: An approximation algorithm for the generalized Steiner problem on networks. In STOC, pages 134--144, 1991. Google ScholarDigital Library
- A. Archer, M. Bateni, M. Hajiaghayi, and H. Karloff. Improved approximation algorithms for prize-collecting Steiner tree and TSP. In FOCS, 2009. Google ScholarDigital Library
- S. Arora. Polynomial time approximation schemes for Euclidean TSP and other geometric problems. In FOCS, page 2, 1996. Google ScholarDigital Library
- S. Arora. Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. J. ACM, 45(5):753--782, 1998. Google ScholarDigital Library
- M. Bateni, M. Hajiaghayi, and D. Marx. Approximation schemes for Steiner forest on planar graphs and graphs of bounded treewidth. CoRR, abs/0911.5143, 2009.Google Scholar
- P. Berman and V. Ramaiyer. Improved approximations for the Steiner tree problem. In SODA, pages 325--334, 1992. Google ScholarDigital Library
- M. Bern and P. Plassmann. The Steiner problem with edge lengths 1 and 2. Information Processing Letters, 32:171--176, 1989. Google ScholarDigital Library
- H. L. Bodlaender. A partial k-arboretum of graphs with bounded treewidth. Theoretical Computer Science, 209(1-2):1--45, 1998. Google ScholarDigital Library
- G. Borradaile, E. D. Demaine, and S. Tazari. Polynomial-time approximation schemes for subset-connectivity problems in bounded genus graphs. In STACS, pages 171--182, 2009.Google Scholar
- G. Borradaile, P. N. Klein, and C. Mathieu. A polynomial-time approximation scheme for Euclidean Steiner forest. In FOCS, pages 115--124, 2008. Google ScholarDigital Library
- G. Borradaile, C. Mathieu, and P. N. Klein. A polynomial-time approximation scheme for Steiner tree in planar graphs. In SODA, pages 1285--1294, 2007. Google ScholarDigital Library
- E. D. Demaine, M. Hajiaghayi, and B. Mohar. Approximation algorithms via contraction decomposition. In SODA, pages 278--287, 2007. Google ScholarDigital Library
- R. Diestel. Graph Theory (Graduate Texts in Mathematics). Springer, August 2005.Google Scholar
- M. R. Garey and D. S. Johnson. The rectilinear Steiner tree problem is NP-complete. SIAM J. Appl. Math., 32(4):826--834, 1977.Google ScholarDigital Library
- E. Gassner. The Steiner forest problem revisited. J. Disc. Alg., In Press, Corrected Proof, 2009. Google ScholarDigital Library
- M. X. Goemans and D. P. Williamson. A general approximation technique for constrained forest problems. SIAM J. Comput., 24(2):296--317, 1995. Google ScholarDigital Library
- S. Hougardy and H. J. Prömel. A 1.598 approximation algorithm for the Steiner problem in graphs. In Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms (SODA), pages 448--453, 1999. Google ScholarDigital Library
- R. M. Karp. On the computational complexity of combinatorial problems. Networks, 5:45--68, 1975.Google ScholarDigital Library
- M. Karpinski and A. Zelikovsky. New approximation algorithms for the Steiner tree problems. J. Comb. Opt., 1(1):47--65, 1997.Google ScholarCross Ref
- P. N. Klein. A linear-time approximation scheme for TSP in undirected planar graphs with edge-weights. SIAM J. Comput., 37(6):1926--1952, 2008. Google ScholarDigital Library
- D. Marx. NP-completeness of list coloring and precoloring extension on the edges of planar graphs. J. Graph Theory, 49(4):313--324, 2005. Google ScholarDigital Library
- D. Marx. Complexity results for minimum sum edge coloring. Discrete Applied Mathematics, 157(5):1034--1045, 2009. Google ScholarDigital Library
- J. S. B. Mitchell. Guillotine subdivisions approximate polygonal subdivisions: A simple polynomial-time approximation scheme for geometric TSP, k-MST, and related problems. SIAM Journal on Computing, 28(4):1298--1309, 1999. Google ScholarDigital Library
- H. J. Prömel and A. Steger. RNC-approximation algorithms for the Steiner problem. In Proceedings of the 14th Annual Symposium on Theoretical Aspects of Computer Science (STACS), pages 559--570, 1997. Google ScholarDigital Library
- M. B. Richey and R. G. Parker. On multiple Steiner subgraph problems. Networks, 16(4):423--438, 1986.Google ScholarCross Ref
- G. Robins and A. Zelikovsky. Tighter bounds for graph Steiner tree approximation. SIAM J. Disc. Math., 19(1):122--134, 2005. Google ScholarDigital Library
- M. Thimm. On the approximability of the Steiner tree problem. Theor. Comput. Sci., 295(1-3):387--402, 2003. Google ScholarDigital Library
- A. Zelikovsky. An 11/6-approximation for the Steiner problem on graphs. In Fourth Czechoslovakian Symp. Combinatorics, Graphs, and Complexity (1990) in Annals of Discrete Mathematics, volume 51, pages 351--354, 1992.Google ScholarCross Ref
- A. Zelikovsky. An 11/6-approximation algorithm for the network Steiner problem. Algorithmica, 9(5):463--470, 1993.Google Scholar
- A. Zelikovsky. Better approximation bounds for the network and Euclidean Steiner tree problems. Technical report, University of Virginia, Charlottesville, VA, USA, 1996. Google ScholarDigital Library
- X. Zhou and T. Nishizeki. The edge-disjoint paths problem is NP-complete for partial k-trees. In Algorithms and computation (Taejon, 1998), pages 417--426. Springer, Berlin, 1998. 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
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 ...
Network Sparsification for Steiner Problems on Planar and Bounded-Genus Graphs
FOCS '14: Proceedings of the 2014 IEEE 55th Annual Symposium on Foundations of Computer ScienceWe propose polynomial-time algorithms that sparsify planar and bounded-genus graphs while preserving optimal or near-optimal solutions to Steiner problems. Our main contribution is a polynomial-time algorithm that, given an unweighted graph G embedded ...
Small Drawings of Outerplanar Graphs, Series-Parallel Graphs, and Other Planar Graphs
In this paper, we study small planar drawings of planar graphs. For arbitrary planar graphs, ź(n2) is the established upper and lower bound on the worst-case area. A long-standing open problem is to determine for what graphs a smaller area can be ...
Comments