Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Speeding Up Dynamic Programming with Representative Sets: An Experimental Evaluation of Algorithms for Steiner Tree on Tree Decompositions

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

Dynamic programming on tree decompositions is a frequently used approach to solve otherwise intractable problems on instances of small treewidth. In recent work by Bodlaender et al. (Proceedings of the 40th international colloquium on automata, languages and programming, ICALP 2013, part I, volume 7965 of Lecture Notes in Computer Science. Springer, Berlin, pp 196–207, 2013), it was shown that for many connectivity problems, there exist algorithms that use time linear in the number of vertices and single exponential in the width of the tree decomposition that is used. The central idea is that it suffices to compute representative sets, and that these can be computed efficiently with help of Gaussian elimination. In this paper, we give an experimental evaluation of this technique for the Steiner Tree problem. Our comparison of the classic dynamic programming algorithm and the improved dynamic programming algorithm that employs table reduction shows that the new approach gives significant improvements on the running time of the algorithm and the size of the tables computed by the dynamic programming algorithm. Thus, the rank-based approach from Bodlaender et al. (2013) does not only give significant theoretical improvements but also is a viable approach in a practical setting, and showcases the potential of exploiting the idea of representative sets for speeding up dynamic programming algorithms. Furthermore, we propose an alternative representation of partial solutions using weighted bit strings in order to circumvent a part of the reduction step that is computationally expensive in practice. In the experimental evaluation we find that this representation yields further significant improvements. We show that the representation can also be used for the other problems fitting in the framework of Bodlaender et al. (2013).

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+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

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

Similar content being viewed by others

Notes

  1. The notation is motivated from lattice theory; it can be observed that the set of all partitions of a set partially ordered by \(\sqsubseteq \) is a lattice (i.e., the inverse of the usual partition lattice), and that \(\sqcap \) is the meet operation of this lattice.

  2. See the proof of Theorem 3.7 in the arXiv report of [5].

  3. In fact, for any lattice we have \(c \sqsubseteq p \sqcap q\) if and only if \(c \sqsubseteq p\) and \(c \sqsubseteq q\).

References

  1. Aneja, Y.P.: An integer linear programming approach to the Steiner problem in graphs. Networks 10, 167–178 (1980)

    Article  MATH  MathSciNet  Google Scholar 

  2. Arnborg, S., Lagergren, J., Seese, D.: Easy problems for tree-decomposable graphs. J. Algorithms 12, 308–340 (1991)

    Article  MATH  MathSciNet  Google Scholar 

  3. Beasley, J.E.: An algorithm for the Steiner problem in graphs. Networks 14, 147–159 (1984)

    Article  MATH  MathSciNet  Google Scholar 

  4. Bodlaender, H.L.: Dynamic programming algorithms on graphs with bounded tree-width. In: Lepistö, T., Salomaa, A. (eds.) Proceedings of the 15th International Colloquium on Automata, Languages and Programming, ICALP’88, Volume 317 of Lecture Notes in Computer Science, pp. 105–119. Springer, Berlin (1988)

    Google Scholar 

  5. Bodlaender, H.L., Cygan, M., Kratsch, S., Nederlof, J.: Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. In: Proceedings of the 40th International Colloquium on Automata, Languages and Programming, ICALP 2013, Part I, Volume 7965 of Lecture Notes in Computer Science, pp. 196–207. Springer, Berlin (2013)

  6. Bodlaender, H.L., Koster, A.M.C.A.: Treewidth computations I. Upper bounds. Inf. Comput. 208, 259–275 (2010)

    Article  MATH  MathSciNet  Google Scholar 

  7. Borie, R.B., Parker, R.G., Tovey, C.A.: Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families. Algorithmica 7, 555–581 (1992)

    Article  MATH  MathSciNet  Google Scholar 

  8. Chimani, M., Mutzel, P., Zey, B.: Improved Steiner tree algorithms for bounded treewidth. J. Discret. Algorithms 16, 67–78 (2012)

    Article  MATH  MathSciNet  Google Scholar 

  9. Cook, W., Seymour, P.D.: Tour merging via branch-decomposition. INFORMS J. Comput. 15(3), 233–248 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  10. Cygan, M., Kratsch, S., Nederlof, J.: Fast Hamiltonicity checking via bases of perfect matchings. In: Proceedings of the 45th Annual Symposium on Theory of Computing, STOC 2013, pp. 301–310 (2013)

  11. Cygan, M., Nederlof, J., Pilipczuk, M., Pilipczuk, M., van Rooij, J., Wojtaszczyk, J. O.: Solving connectivity problems parameterized by treewidth in single exponential time. In: Proceedings of the 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, pp. 150–159 (2011)

  12. Duin, C.: Steiner problems in graphs. Ph.D. thesis, University of Amsterdam, Amsterdam, The Netherlands (1993)

  13. Fafianie, S., Bodlaender, H.L., Nederlof, J.: Speeding-up dynamic programming with representative sets: an experimental evaluation of algorithms for Steiner tree on tree decompositions. Report on arXiv:1305.7448 (2013)

  14. Fomin, F.V., Lokshtanov, D., Saurabh, S.: Efficient computation of representative sets with applications in parameterized and exact algorithms. In: Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, pp. 142–151

  15. Hanan, M.: On Steiner’s problem with rectilinear distance. SIAM J. Appl. Math. 14, 255–265 (1966)

    Article  MATH  MathSciNet  Google Scholar 

  16. Hwang, F., Richards, D.S., Winter, P.: The Steiner Tree Problem, Volume 53 of Annals of Discrete Mathematics. Elsevier, Amsterdam (1992)

    Google Scholar 

  17. Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W. (eds.) Complexity of Computer Computations, pp. 85–104. Plenum Press, New York (1972)

    Chapter  Google Scholar 

  18. Kloks, T.: Treewidth. Computations and Approximations, Volume 842 of Lecture Notes in Computer Science. Springer, Berlin (1994)

    Google Scholar 

  19. Koch, T., Martin, A., Voß, S.: Steinlib, an updated library on Steiner tree problems in graphs. Technical Report ZIB-Report 00–37, Konrad-Zuse Zentrum für Informationstechnik Berlin. http://elib.zib.de/steinlib (2000)

  20. Korach, E., Solel, N.: Linear time algorithm for minimum weight Steiner tree in graphs with bounded treewidth. Technical Report 632, Technion, Haifa, Israel (1990)

  21. Lovász, L.: Flats in matroids and geometric graphs. In: Combinatorial Surveys. Proceedings 6th Britisch Combinatorial Conference, pp. 45–86. Academic Press, London (1977)

  22. Marx, D.: A parameterized view on matroid optimization problems. Theoret. Comput. Sci. 410, 4471–4479 (2009)

    Article  MATH  MathSciNet  Google Scholar 

  23. Monien, B.: How to find long paths efficiently. Ann. Discret. Math. 25, 239–254 (1985)

    MathSciNet  Google Scholar 

  24. Robertson, N., Seymour, P.D.: Graph minors. II. Algorithmic aspects of tree-width. J. Algorithms 7, 309–322 (1986)

    Article  MATH  MathSciNet  Google Scholar 

  25. Telle, J., Proskurowski, A.: Efficient sets in partial \(k\)-trees. Discret. Appl. Math. 44, 109–117 (1993)

    Article  MATH  MathSciNet  Google Scholar 

  26. Treewidthlib. http://www.cs.uu.nl/people/hansb/treewidthlib (2004)

  27. Wald, J.A., Colbourn, C.J.: Steiner trees, partial 2-trees, and minimum IFI networks. Networks 13, 159–167 (1983)

    Article  MATH  MathSciNet  Google Scholar 

  28. Warme, D., Winter, P., Zachariasen, M.: GeoSteiner, software for computing Steiner trees. http://www.diku.dk/hjemmesider/ansatte/martinz/geosteiner/

  29. Wei-Kleiner, F.: Tree decomposition based Steiner tree computation over large graphs. Report on arXiv:1305.5757 (2013)

  30. Winter, P.: Steiner problem in networks: a survey. Networks 17, 129–167 (1987)

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Utrecht University, Utrecht, The Netherlands

    Stefan Fafianie, Hans L. Bodlaender & Jesper Nederlof

Authors
  1. Stefan Fafianie
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Hans L. Bodlaender
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Jesper Nederlof
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Hans L. Bodlaender.

Additional information

The third author is supported by the NWO Project ‘Space and Time Efficient Structural Improvements of Dynamic Programming Algorithms’.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Fafianie, S., Bodlaender, H.L. & Nederlof, J. Speeding Up Dynamic Programming with Representative Sets: An Experimental Evaluation of Algorithms for Steiner Tree on Tree Decompositions. Algorithmica 71, 636–660 (2015). https://doi.org/10.1007/s00453-014-9934-0

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00453-014-9934-0

Keywords

Search

Navigation