Document Open Access Logo

Three Is Enough for Steiner Trees

Authors Emmanuel Arrighi , Mateus de Oliveira Oliveira

PDF
Thumbnail PDF

File

LIPIcs.SEA.2021.5.pdf
  • Filesize: 0.8 MB
  • 15 pages

Document Identifiers

Author Details

Emmanuel Arrighi
  • University of Bergen, Norway
Mateus de Oliveira Oliveira
  • University of Bergen, Norway

Funding

  • Arrighi, Emmanuel: Research Council of Norway (Grant no. 274526).
  • de Oliveira Oliveira, Mateus: Research Council of Norway (Grant no. 288761) and Sigma2 Network (NN9535K).

Cite As Get BibTex

Emmanuel Arrighi and Mateus de Oliveira Oliveira. Three Is Enough for Steiner Trees. In 19th International Symposium on Experimental Algorithms (SEA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 190, pp. 5:1-5:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.SEA.2021.5

Abstract

In the Steiner tree problem, the input consists of an edge-weighted graph G together with a set S of terminal vertices. The goal is to find a minimum weight tree in G that spans all terminals. This fundamental NP-hard problem has direct applications in many subfields of combinatorial optimization, such as planning, scheduling, etc. In this work we introduce a new heuristic for the Steiner tree problem, based on a simple routine for improving the cost of sub-optimal Steiner trees: first, the sub-optimal tree is split into three connected components, and then these components are reconnected by using an algorithm that computes an optimal Steiner tree with 3-terminals (the roots of the three components). We have implemented our heuristic into a solver and compared it with several state-of-the-art solvers on well-known data sets. Our solver performs very well across all the data sets, and outperforms most of the other benchmarked solvers on very large graphs, which have been either obtained from real-world applications or from randomly generated data sets.

Subject Classification

ACM Subject Classification
  • Theory of computation → Theory of randomized search heuristics
Keywords
  • Steiner Tree
  • Heuristics
  • 3TST

Metrics

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

Supplementary Materials

References

  1. Piotr Berman and Viswanathan Ramaiyer. Improved approximations for the steiner tree problem. J. Algorithms, 17(3):381-408, 1994. Google Scholar
  2. Marshall W. Bern and Paul E. Plassmann. The steiner problem with edge lengths 1 and 2. Inf. Process. Lett., 32(4):171-176, 1989. Google Scholar
  3. Édouard Bonnet and Florian Sikora. The PACE 2018 Parameterized Algorithms and Computational Experiments Challenge: The Third Iteration. In Proc. of IPEC 2018, volume 115, pages 26:1-26:15, 2019. Google Scholar
  4. Jaroslaw Byrka, Fabrizio Grandoni, Thomas Rothvoß, and Laura Sanità. Steiner tree approximation via iterative randomized rounding. J. ACM, 60(1):6:1-6:33, 2013. Google Scholar
  5. Goutam Chakraborty. Genetic algorithm approaches to solve various steiner tree problems. In Steiner Trees in Industry, pages 29-69. Springer, 2001. Google Scholar
  6. Xiuzhen Cheng, Yingshu Li, Ding-Zhu Du, and Hung Q Ngo. Steiner trees in industry. In Handbook of combinatorial optimization, pages 193-216. Springer, 2004. Google Scholar
  7. Mung Chiang, Henry Lam, Zhenming Liu, and H. Vincent Poor. Why steiner-tree type algorithms work for community detection. In Proc. of (AISTATS 2013), volume 31, pages 187-195, 2013. Google Scholar
  8. Diego de Uña, Graeme Gange, Peter Schachte, and Peter J Stuckey. Steiner tree problems with side constraints using constraint programming. In Proc. of the 30th AAAI Conference on Artificial Intelligence, 2016. Google Scholar
  9. Pavel Dvorák, Andreas Emil Feldmann, Dusan Knop, Tomás Masarík, Tomas Toufar, and Pavel Veselý. Parameterized approximation schemes for steiner trees with small number of steiner vertices. In Proc. of (STACS 2018), volume 96, pages 26:1-26:15, 2018. Google Scholar
  10. Ambros Gleixner, Leon Eifler, Tristan Gally, Gerald Gamrath, Patrick Gemander, Robert Lion Gottwald, Gregor Hendel, Christopher Hojny, Thorsten Koch, Matthias Miltenberger, Benjamin Müller, Marc E. Pfetsch, Christian Puchert, Daniel Rehfeldt, Franziska Schlösser, Felipe Serrano, Yuji Shinano, Jan Merlin Viernickel, Stefan Vigerske, Dieter Weninger, Jonas T. Witt, and Jakob Witzig. The SCIP Optimization Suite 5.0. ZIB-Report 17-61, Zuse Institute Berlin, December 2017. URL: http://nbn-resolving.de/urn:nbn:de:0297-zib-66297.
  11. S Louis Hakimi. Steiner’s problem in graphs and its implications. Networks, 1(2):113-133, 1971. Google Scholar
  12. Stefan Hougardy and Hans Jürgen Prömel. A 1.598 approximation algorithm for the steiner problem in graphs. In Proc. of the 10th Symposium on Discrete Algorithms (SODA 1999), pages 448-453, 1999. Google Scholar
  13. Rostam Joobbani. An artificial intelligence approach to VLSI routing, volume 9. Springer Science & Business Media, 2012. Google Scholar
  14. Richard M. Karp. Reducibility among combinatorial problems. In Proc. of Complexity of Computer Computations, The IBM Research Symposia Series, pages 85-103, 1972. Google Scholar
  15. Marek Karpinski and Alexander Zelikovsky. New approximation algorithms for the steiner tree problems. J. Comb. Optim., 1(1):47-65, 1997. Google Scholar
  16. Emil Keyder and Hector Geffner. Trees of shortest paths vs. steiner trees: Understanding and improving delete relaxation heuristics. In Proc. of the 21st International Joint Conference on Artificial Intelligence (IJCAI 2009), pages 1734-1739, 2009. Google Scholar
  17. Theodoros Lappas, Kun Liu, and Evimaria Terzi. Finding a team of experts in social networks. In Proc. of 15th International Conference on Knowledge Discovery and Data Mining (KDD 2009), pages 467-476, 2009. Google Scholar
  18. Sookyoung Lee and Mohamed F. Younis. Recovery from multiple simultaneous failures in wireless sensor networks using minimum steiner tree. J. Parallel Distrib. Comput., 70(5):525-536, 2010. Google Scholar
  19. M Lundy. Applications of the annealing algorithm to combinatorial problems in statistics. Biometrika, 72(1):191-198, 1985. Google Scholar
  20. Mohamed El Bachir Menai. A logic-based approach to solve the steiner tree problem. In IFIP International Conference on Artificial Intelligence Applications and Innovations, pages 73-79. Springer, 2009. Google Scholar
  21. Hans Jürgen Prömel and Angelika Steger. Rnc-approximation algorithms for the steiner problem. In Proc. of the 14th Annual Symposium on Theoretical Aspects of Computer Science (STACS 1997), Proceedings, volume 1200 of LNCS, pages 559-570, 1997. Google Scholar
  22. Daniel Rehfeldt, Thorsten Koch, and Stephen J. Maher. Reduction techniques for the prize collecting steiner tree problem and the maximum-weight connected subgraph problem. Networks, 73(2):206-233, 2019. URL: https://doi.org/10.1002/net.21857.
  23. Urban Road Networks. Urban road network data, January 2016. URL: https://doi.org/10.6084/m9.figshare.2061897.v1.
  24. Gabriel Robins and Alexander Zelikovsky. Improved steiner tree approximation in graphs. In Proc. of the 11th Symposium on Discrete Algorithms (SODA 2000), pages 770-779, 2000. Google Scholar
  25. Gabriel Robins and Alexander Zelikovsky. Tighter bounds for graph steiner tree approximation. SIAM J. Discrete Math., 19(1):122-134, 2005. Google Scholar
  26. Ryan A. Rossi and Nesreen K. Ahmed. The network data repository with interactive graph analytics and visualization. In AAAI, 2015. URL: http://networkrepository.com.
  27. Hiromitsu Takahashi. An approximate solution for the steiner problem in graphs. Math. Japonica., 6:573-577, 1990. Google Scholar
  28. 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.
  29. Alexander Zelikovsky. An 11/6-approximation algorithm for the network steiner problem. Algorithmica, 9(5):463-470, 1993. Google Scholar
  30. Alexander Zelikovsky. Better approximation bounds for the network and euclidean steiner tree problems. University of Virginia, Charlottesville, VA, 1996. Google Scholar
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 About DROPS Imprint Privacy Contact