这是indexloc提供的服务，不要输入任何密码
Skip to main content
Springer Nature Link
Log in

Computing Optimal Steiner Trees in Polynomial Space

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

Given an n-node edge-weighted graph and a subset of k terminal nodes, the NP-hard (weighted) Steiner tree problem is to compute a minimum-weight tree which spans the terminals. All the known algorithms for this problem which improve on trivial O(1.62n)-time enumeration are based on dynamic programming, and require exponential space.

Motivated by the fact that exponential-space algorithms are typically impractical, in this paper we address the problem of designing faster polynomial-space algorithms. Our first contribution is a simple O((27/4)k n O(logk))-time polynomial-space algorithm for the problem. This algorithm is based on a variant of the classical tree-separator theorem: every Steiner tree has a node whose removal partitions the tree in two forests, containing at most 2k/3 terminals each. Exploiting separators of logarithmic size which evenly partition the terminals, we are able to reduce the running time to \(O(4^{k}n^{O(\log^{2} k)})\). This improves on trivial enumeration for roughly k<n/3, which covers most of the cases of practical interest. Combining the latter algorithm (for small k) with trivial enumeration (for large k) we obtain a O(1.59n)-time polynomial-space algorithm for the weighted Steiner tree problem.

As a second contribution of this paper, we present a O(1.55n)-time polynomial-space algorithm for the cardinality version of the problem, where all edge weights are one. This result is based on a improved branching strategy. The refined branching is based on a charging mechanism which shows that, for large values of k, convenient local configurations of terminals and non-terminals exist. The analysis of the algorithm relies on the Measure & Conquer approach: the non-standard measure used here is a linear combination of the number of nodes and number of non-terminals. Using a recent result in Nederlof (International colloquium on automata, languages and programming (ICALP), pp. 713–725, 2009), the running time can be reduced to O(1.36n). The previous best algorithm for the cardinality case runs in O(1.42n) time and exponential space.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+
from $39.99 /Month
  • Starting from 10 chapters or articles per month
  • Access and download chapters and articles from more than 300k books and 2,500 journals
  • Cancel anytime
View plans

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5

Similar content being viewed by others

Explore related subjects

Discover the latest articles, books and news in related subjects, suggested using machine learning.

Notes

  1. Throughout this paper we use the O ∗ notation which suppresses polynomial factors: for any polynomial p(n), O(p(n)T) is O ∗(T).

  2. Throughout this paper, logx stands for log2 x.

  3. We recall that the metric closure of a weighted graph G=(V,E) is a complete graph on node-set V, with weights given by the shortest path distances with respect to original weights.

References

  1. Arora, S.: Polynomial time approximation schemes for Euclidean TSP and other geometric problems. J. ACM 45, 753–782 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  2. Bax, E.T.: Inclusion and exclusion algorithm for the Hamiltonian path problem. Inf. Process. Lett. 47, 203–207 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  3. Bern, M., Plassmann, P.: The Steiner tree problem with edge lengths 1 and 2. Inf. Process. Lett. 32, 171–176 (1989)

    Article  MathSciNet  MATH  Google Scholar 

  4. Björklund, A., Husfeldt, T.: Inclusion-exclusion algorithms for counting set partitions. In: IEEE Symposium on Foundations of Computer Science (FOCS), pp. 575–582 (2006)

    Google Scholar 

  5. Björklund, A., Husfeldt, T., Kaski, P., Koivisto, M.: Fourier meets Möbious: fast subset convolution. In: ACM Symposium on Theory of Computing (STOC), pp. 67–74 (2007)

    Google Scholar 

  6. Blelloch, G.E., Dhamdhere, K., Halperin, E., Ravi, R., Schwartz, R., Sridhar, S.: Fixed parameter tractability of binary near-perfect phylogenetic tree reconstruction. In: International Colloquium on Automata, Languages and Programming (ICALP), pp. 667–678 (2006)

    Chapter  Google Scholar 

  7. Bodlaender, H.L.: A partial k-arboretum of graphs with bounded treewidth. Theor. Comput. Sci. 209, 1–45 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  8. Byrka, J., Grandoni, F., Rothvoß, T., Sanità, L.: An improved LP-based approximation for Steiner tree. In: ACM Symposium on Theory of Computing (STOC), Best Paper Award (2010, to appear). doi:10.1145/1806689.1806769

  9. Deneen, L.L., Shute, G.M., Thomborson, C.D.: A probably fast, provably optimal algorithm for rectilinear Steiner trees. Random Struct. Algorithms 5(4), 535–557 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  10. Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, New York (1999)

    Book  Google Scholar 

  11. Dreyfus, S.E., Wagner, R.A.: The Steiner problem in graphs. Networks 1, 195–207 (1971/72)

    Article  MathSciNet  Google Scholar 

  12. Eppstein, D.: Improved algorithms for 3-coloring, 3-edge-coloring, and constraint satisfaction. In: ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 329–337 (2001)

    Google Scholar 

  13. Eppstein, D.: Quasiconvex analysis of multivariate recurrence equations for backtracking algorithms. ACM Trans. Algorithms 2(4), 492–509 (2006)

    Article  MathSciNet  Google Scholar 

  14. Eppstein, D.: The traveling salesman problem for cubic graphs. J. Graph Algorithms Appl. 11(1), 61–81 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  15. Flum, J., Grohe, M.: Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer, Berlin (2006)

    Google Scholar 

  16. Fomin, F.V., Gaspers, S., Pyatkin, A.V., Razgon, I.: On the minimum feedback vertex set problem: exact and enumeration algorithms. Algorithmica 52(2), 293–307 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  17. Fomin, F.V., Grandoni, F., Kratsch, D.: Measure and conquer: domination—a case study. In: International Colloquium on Automata, Languages and Programming (ICALP), pp. 191–203 (2005)

    Chapter  Google Scholar 

  18. Fomin, F.V., Grandoni, F., Kratsch, D.: Measure and conquer: a simple O(20.288n) independent set algorithm. In: ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 18–25 (2006)

    Chapter  Google Scholar 

  19. Fomin, F.V., Grandoni, F., Kratsch, D.: Faster Steiner tree computation in polynomial-space. In: European Symposium on Algorithms (ESA), pp. 430–441 (2008)

    Google Scholar 

  20. Fomin, F.V., Grandoni, F., Kratsch, D.: Solving connected dominating set faster than 2n. Algorithmica 52, 153–166 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  21. Fomin, F.V., Grandoni, F., Kratsch, D.: A measure & conquer approach for the analysis of exact algorithms. J. ACM 56(5) (2009). doi:10.1145/1552285.1552286

  22. Fomin, F.V., Grandoni, F., Pyatkin, A., Stepanov, A.: Combinatorial bounds via measure and conquer: bounding minimal dominating sets and applications. ACM Trans. Algorithms 5(1) (2008). doi:10.1145/1435375.1435384

  23. Fuchs, B., Kern, W., Mölle, D., Richter, S., Rossmanith, P., Wang, X.: Dynamic programming for minimum Steiner trees. Theory Comput. Syst. 41(3), 493–500 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  24. Ganley, J.L.: Computing optimal rectilinear Steiner trees: a survey and experimental evaluation. Discrete Appl. Math. 90(1–3), 161–171 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  25. Garey, M.R., Johnson, D.S.: The rectilinear Steiner tree problem is NP-complete. SIAM J. Appl. Math. 32, 826–834 (1977)

    Article  MathSciNet  MATH  Google Scholar 

  26. Garey, M.R., Johnson, D.S.: Computers and Intractability. A Guide to the Theory of NP-Completeness. Freemann, New York (1979)

    MATH  Google Scholar 

  27. Grandoni, F.: Exact algorithms for hard graph problems. PhD thesis, Università di Roma Tor Vergata, Roma, Italy, Mar. 2004

  28. Grandoni, F.: A note on the complexity of minimum dominating set. J. Discrete Algorithms 4(2), 209–214 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  29. Guo, J., Niedermeier, R., Wernicke, S.: Parameterized complexity of generalized vertex cover problems. In: International Workshop on Algorithms and Data Structures (WADS), pp. 36–48. Springer, Berlin (2005)

    Chapter  Google Scholar 

  30. Gurevich, Y., Shelah, S.: Expected computation time for Hamiltonian path problem. SIAM J. Comput. 16(3), 486–502 (1987)

    Article  MathSciNet  MATH  Google Scholar 

  31. Hwang, F.K., Richards, D.S., Winter, P.: The Steiner Tree Problem. North-Holland, Amsterdam (1992)

    MATH  Google Scholar 

  32. Kahng, A., Robins, G.: On Optimal Interconnections for VLSI. Kluwer, Dordrecht (1995)

    MATH  Google Scholar 

  33. Karp, R.M.: Dynamic programming meets the principle of inclusion and exclusion. Oper. Res. Lett. 1, 49–51 (1982)

    Article  MathSciNet  MATH  Google Scholar 

  34. Korte, B., Prömel, H.J., Steger, A.: Steiner trees in VLSI-layout. In: Paths, Flows, and VLSI-Layout, pp. 185–214 (1990)

    Google Scholar 

  35. Mölle, D., Richter, S., Rossmanith, P.: A faster algorithm for the Steiner tree problem. In: Symposium on Theoretical Aspects of Computer Science (STACS), pp. 561–570 (2006)

    Google Scholar 

  36. Nederlof, J.: Fast polynomial-space algorithms using Mobius inversion: improving on Steiner tree and related problems. In: International Colloquium on Automata, Languages and Programming (ICALP), pp. 713–725 (2009)

    Chapter  Google Scholar 

  37. Niedermeier, R.: Invitation to fixed-parameter algorithms. Oxford Lecture Series in Mathematics and Its Applications, vol. 31. Oxford University Press, Oxford (2006)

    Book  MATH  Google Scholar 

  38. Prömel, H.J., Steger, A.: The Steiner Tree Problem. Advanced Lectures in Mathematics. Vieweg, Braunschweig (2002)

    Book  Google Scholar 

  39. Robins, G., Zelikovsky, A.: Improved Steiner tree approximation in graphs. In: ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 770–779 (2000)

    Google Scholar 

  40. Woeginger, G.: Space and time complexity of exact algorithms: some open problems. In: International Workshop on Parameterized and Exact Computation (IWPEC), pp. 281–290 (2004)

    Chapter  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Informatics, University of Bergen, 5020, Bergen, Norway

    Fedor V. Fomin & Daniel Lokshtanov

  2. IDSIA, University of Italian Switzerland, Galleria 1, 6928, Manno, Switzerland

    Fabrizio Grandoni

  3. LITA, Université Paul Verlaine – Metz, 57045, Metz Cedex 01, France

    Dieter Kratsch

  4. The Institute of Mathematical Sciences, Taramani, Chennai, 600 113, India

    Saket Saurabh

Authors
  1. Fedor V. Fomin
    View author publications

    Search author on:PubMed Google Scholar

  2. Fabrizio Grandoni
    View author publications

    Search author on:PubMed Google Scholar

  3. Dieter Kratsch
    View author publications

    Search author on:PubMed Google Scholar

  4. Daniel Lokshtanov
    View author publications

    Search author on:PubMed Google Scholar

  5. Saket Saurabh
    View author publications

    Search author on:PubMed Google Scholar

Corresponding author

Correspondence to Fabrizio Grandoni.

Additional information

A preliminary version of this paper appeared in ESA’08 [19].

Rights and permissions

Reprints and permissions

About this article

Cite this article

Fomin, F.V., Grandoni, F., Kratsch, D. et al. Computing Optimal Steiner Trees in Polynomial Space. Algorithmica 65, 584–604 (2013). https://doi.org/10.1007/s00453-012-9612-z

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue date:

  • DOI: https://doi.org/10.1007/s00453-012-9612-z

Keywords