Document Open Access Logo

Approximation Algorithms for Steiner Tree Based on Star Contractions: A Unified View

Authors Radek Hušek, Dušan Knop , Tomáš Masařk

PDF
Thumbnail PDF

File

LIPIcs.IPEC.2020.16.pdf
  • Filesize: 0.92 MB
  • 18 pages

Document Identifiers

Author Details

Radek Hušek
  • Computer Science Institute of Charles University, Faculty of Mathematics and Physics, Charles University, Prague, Czech Republic
Dušan Knop
  • Department of Theoretical Computer Science, Faculty of Information Technology, Czech Technical University in Prague, Czech Republic
Tomáš Masařk
  • Faculty of Mathematics, Informatics and Mechanics, University of Warsaw, Poland
  • Department of Applied Mathematics, Faculty of Mathematics and Physics, Charles University, Czech Republic

Funding

Students were supported by Charles University student grant SVV-2017-260452 and GAUK 1514217.
  • Knop, Dušan: Supported by the OP VVV MEYS funded project CZ.02.1.01/0.0/0.0/16_019/0000765 "Research Center for Informatics".
  • Masařk, Tomáš: have received funding from the European Research Council under the European Union’s Horizon 2020 research and innovation programme Grant Agreement 714704.

Acknowledgements

We thank the authors of the Boost library [Jeremy G. Siek et al., 2002], which we use in our code, for their work and effective implementation of many graph algorithms. We thank Tomáš Toufar for consultations in the early stages of preparation of the experiments in the paper as well as for the implementation of a part [Hušek et al., 2018] which was partially used in our code. We thank the PACE challenge which was a good motivation and inspiration for the development of practical algorithms for the Steiner Tree problem. The results of this challenge motivated us to develop the experiments presented in this paper. We also thank anonymous referees for interesting feedback as well as for pointing us to several interesting directions for future improvements and related results. Part of the work was carried out while D. Knop and T. Masařík were at the University of Bergen.

Cite AsGet BibTex

Radek Hušek, Dušan Knop, and Tomáš Masařk. Approximation Algorithms for Steiner Tree Based on Star Contractions: A Unified View. In 15th International Symposium on Parameterized and Exact Computation (IPEC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 180, pp. 16:1-16:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.IPEC.2020.16

Abstract

In the Steiner Tree problem, we are given an edge-weighted undirected graph G = (V,E) and a set of terminals R ⊆ V. The task is to find a connected subgraph of G containing R and minimizing the sum of weights of its edges. Steiner Tree is well known to be NP-complete and is undoubtedly one of the most studied problems in (applied) computer science. We observe that many approximation algorithms for Steiner Tree follow a similar scheme (meta-algorithm) and perform (exhaustively) a similar routine which we call star contraction. Here, by a star contraction, we mean finding a star-like subgraph in (the metric closure of) the input graph minimizing the ratio of its weight to the number of contained terminals minus one; and contract. It is not hard to see that the well-known MST-approximation seeks the best star to contract among those containing two terminals only. Zelikovsky’s approximation algorithm follows a similar workflow, finding the best star among those containing three terminals. We perform an empirical study of star contractions with the relaxed condition on the number of terminals in each star contraction motivated by a recent result of Dvořák et al. [Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices, STACS 2018]. Furthermore, we propose two improvements of Zelikovsky’s 11/6-approximation algorithm and we empirically confirm that the quality of the solution returned by any of these is better than the one returned by the former algorithm. However, such an improvement is exchanged for a slower running time (up to a multiplicative factor of the number of terminals).

Subject Classification

ACM Subject Classification
  • Theory of computation → Graph algorithms analysis
Keywords
  • Steiner tree
  • approximation
  • star contractions
  • minimum spanning tree

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

Supplementary Materials

References

  1. 11th DIMACS Implementation Challenge, 2011. URL: http://dimacs11.zib.de/.
  2. PACE Challenge 2018, 2018. URL: https://pacechallenge.wordpress.com/pace-2018/.
  3. John E. Beasley. Or-library: Distributing test problems by electronic mail. Journal of the Operational Research Society, 41(11):1069-1072, 1990. URL: https://doi.org/10.1057/jors.1990.166.
  4. Stephan Beyer and Markus Chimani. Strong steiner tree approximations in practice. ACM J. Exp. Algorithmics, 24(1), January 2019. URL: https://doi.org/10.1145/3299903.
  5. Édouard Bonnet and Florian Sikora. The PACE 2018 Parameterized Algorithms and Computational Experiments Challenge: The Third Iteration. In Christophe Paul and Michał Pilipczuk, editors, 13th International Symposium on Parameterized and Exact Computation (IPEC 2018), volume 115 of Leibniz International Proceedings in Informatics (LIPIcs), pages 26:1-26:15, Dagstuhl, Germany, 2019. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.IPEC.2018.26.
  6. Al Borchers and Ding-Zhu Du. Thek-steiner ratio in graphs. SIAM Journal on Computing, 26(3):857-869, 1997. URL: https://doi.org/10.1137/S0097539795281086.
  7. Jarosław Byrka, Fabrizio Grandoni, Thomas Rothvoss, and Laura Sanità. Steiner Tree Approximation via Iterative Randomized Rounding. Journal of the ACM, 60(1):1-33, February 2013. URL: https://doi.org/10.1145/2432622.2432628.
  8. Markus Chimani and Matthias Woste. Contraction-based steiner tree approximations in practice. In Algorithms and Computation, pages 40-49. Springer Berlin Heidelberg, 2011. URL: https://doi.org/10.1007/978-3-642-25591-5_6.
  9. Marcus Poggi de Aragão and Renato F. Werneck. On the implementation of MST-based heuristics for the steiner problem in graphs. In Algorithm Engineering and Experiments, pages 1-15. Springer Berlin Heidelberg, 2002. URL: https://doi.org/10.1007/3-540-45643-0_1.
  10. Reinhard Diestel. Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics. Springer, 2012. Google Scholar
  11. Edsger W. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik, 1(1):269-271, December 1959. URL: https://doi.org/10.1007/BF01386390.
  12. Stuart E. Dreyfus and Robert A. Wagner. The steiner problem in graphs. Networks, 1(3):195-207, 1971. URL: https://doi.org/10.1002/net.3230010302.
  13. Cees Duin. Steiner’s problem in graphs. PhD thesis, University of Amsterdam, 1993. Google Scholar
  14. Cees Duin. Preprocessing the Steiner Problem in Graphs, pages 175-233. Springer US, Boston, MA, 2000. URL: https://doi.org/10.1007/978-1-4757-3171-2_10.
  15. Pavel Dvořák, Andreas Emil Feldmann, Dušan Knop, Tomáš Masařík, Tomáš Toufar, and Pavel Veselý. Parameterized approximation schemes for steiner trees with small number of steiner vertices. In Rolf Niedermeier and Brigitte Vallée, editors, 35th Symposium on Theoretical Aspects of Computer Science, STACS 2018, February 28 to March 3, 2018, Caen, France, volume 96 of LIPIcs, pages 26:1-26:15. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.STACS.2018.26.
  16. Bernhard Fuchs, Walter Kern, Daniel Mölle, Stefan Richter, Peter Rossmanith, and Xinhui Wang. Dynamic programming for minimum steiner trees. Theory Comput. Syst., 41(3):493-500, 2007. URL: https://doi.org/10.1007/s00224-007-1324-4.
  17. Gerald Gamrath, Thorsten Koch, Stephen J. Maher, Daniel Rehfeldt, and Yuji Shinano. Scip-jack - a solver for STP and variants with parallelization extensions. Math. Program. Comput., 9(2):231-296, 2017. URL: https://doi.org/10.1007/s12532-016-0114-x.
  18. Stefan Hougardy, Jannik Silvanus, and Jens Vygen. Dijkstra meets steiner: a fast exact goal-oriented steiner tree algorithm. Mathematical Programming Computation, 9(2):135-202, June 2017. URL: https://doi.org/10.1007/s12532-016-0110-1.
  19. Radek Hušek, Dušan Knop, and Tomáš Masařík. Approximation algorithms for steiner tree based on star contractions: A unified view, 2020. URL: http://arxiv.org/abs/2002.03583.
  20. Radek Hušek, Tomáš Toufar, Dušan Knop, Tomáš Masařík, and Eduard Eiben. Steiner tree heuristics for PACE 2018 Challenge track C, 2018. URL: https://github.com/goderik01/PACE2018.
  21. Frank K. Hwang, Dana S. Richards, and Pawel Winter. The Steiner tree problem, volume 53. Elsevier, 1992. URL: https://doi.org/10.1016/s0167-5060(08)x7008-6.
  22. Richard M. Karp. Reducibility among combinatorial problems. In Complexity of computer computations, pages 85-103. Plenum, 1972. URL: https://doi.org/10.1007/978-1-4684-2001-2_9.
  23. Thorsten Koch and Alexander Martin. Solving steiner tree problems in graphs to optimality. Networks, 32(3):207-232, 1998. URL: https://doi.org/10.1002/(SICI)1097-0037(199810)32:3<207::AID-NET5>3.0.CO;2-O.
  24. Thorsten Koch and Daniel Rehfeldt. SCIP-jack, 2018. URL: https://github.com/dRehfeldt/scipjack/.
  25. Lawrence Kou, George Markowsky, and Leonard Berman. A fast algorithm for steiner trees. Acta Informatica, 15(2):141-145, June 1981. URL: https://doi.org/10.1007/BF00288961.
  26. Jiří Matoušek and Jaroslav Nešetřil. Invitation to Discrete Mathematics. Oxford University Press, Inc., New York, NY, USA, 1998. Google Scholar
  27. Kurt Mehlhorn. A faster approximation algorithm for the Steiner problem in graphs. Information Processing Letters, 27(3):125-128, 1988. URL: https://doi.org/10.1016/0020-0190(88)90066-X.
  28. Michael Ian Shamos and Dan Hoey. Closest-point problems. In 16th Annual Symposium on Foundations of Computer Science, Berkeley, California, USA, October 13-15, 1975, pages 151-162, 1975. URL: https://doi.org/10.1109/SFCS.1975.8.
  29. Jeremy G. Siek, Lie-Quan Lee, and Andrew Lumsdaine. The Boost Graph Library: User Guide and Reference Manual. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 2002. Google Scholar
  30. Eduardo Uchoa, Marcus Poggi de Aragão, and Celso C. Ribeiro. Preprocessing Steiner problems from VLSI layout. Networks, 40(1):38-50, 2002. URL: https://doi.org/10.1002/net.10035.
  31. Dimitri Watel and Marc-Antoine Weisser. A practical greedy approximation for the directed steiner tree problem. Journal of Combinatorial Optimization, 32(4):1327-1370, November 2016. URL: https://doi.org/10.1007/s10878-016-0074-0.
  32. Jeffery Westbrook and Robert E. Tarjan. Maintaining bridge-connected and biconnected components on-line. Algorithmica, 7(1):433-464, June 1992. URL: https://doi.org/10.1007/BF01758773.
  33. Alexander Z. Zelikovsky. An 11/6-approximation algorithm for the network steiner problem. Algorithmica, 9(5), 1993. URL: https://doi.org/10.1007/BF01187035.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact