Document Open Access Logo

Algorithms for 2-Connected Network Design and Flexible Steiner Trees with a Constant Number of Terminals

Authors Ishan Bansal, Joe Cheriyan, Logan Grout, Sharat Ibrahimpur

PDF

File

Thumbnail PDF
PDF
LIPIcs.APPROX-RANDOM.2023.14.pdf
  • Filesize: 0.83 MB
  • 14 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Approximation algorithms analysis
Keywords
  • Approximation algorithms
  • Capacitated network design
  • Network design
  • Parametrized algorithms
  • Steiner cycle problem
  • Steiner 2-edge connected subgraphs
  • Steiner 2-node connected subgraphs

Metrics

Abstract

The k-Steiner-2NCS problem is as follows: Given a constant (positive integer) k, and an undirected connected graph G = (V,E), non-negative costs c on the edges, and a partition (T, V⧵T) of V into a set of terminals, T, and a set of non-terminals (or, Steiner nodes), where |T| = k, find a min-cost two-node connected subgraph that contains the terminals. The k-Steiner-2ECS problem has the same inputs; the algorithmic goal is to find a min-cost two-edge connected subgraph that contains the terminals.
We present a randomized polynomial-time algorithm for the unweighted k-Steiner-2NCS problem, and a randomized FPTAS for the weighted k-Steiner-2NCS problem. We obtain similar results for a capacitated generalization of the k-Steiner-2ECS problem.
Our methods build on results by Björklund, Husfeldt, and Taslaman (SODA 2012) that give a randomized polynomial-time algorithm for the unweighted k-Steiner-cycle problem; this problem has the same inputs as the unweighted k-Steiner-2NCS problem, and the algorithmic goal is to find a min-cost simple cycle C that contains the terminals (C may contain any number of Steiner nodes).

Cite As Get BibTex

Ishan Bansal, Joe Cheriyan, Logan Grout, and Sharat Ibrahimpur. Algorithms for 2-Connected Network Design and Flexible Steiner Trees with a Constant Number of Terminals. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 14:1-14:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2023.14

Author Details

Ishan Bansal
  • Operations Research and Information Engineering, Cornell University, Ithaca, NY, USA
Joe Cheriyan
  • Department of Combinatorics and Optimization, University of Waterloo, Canada
Logan Grout
  • Operations Research and Information Engineering, Cornell University, Ithaca, NY, USA
Sharat Ibrahimpur
  • Department of Mathematics, London School of Economics and Political Science, UK

Funding

  • Cheriyan, Joe: Supported in part by NSERC, RGPIN-2019-04197.
  • Ibrahimpur, Sharat: Received funding from the following sources: NSERC grant 327620-09 and an NSERC DAS Award, European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement no. ScaleOpt–757481), and Dutch Research Council NWO Vidi Grant 016.Vidi.189.087.

References

  1. David Adjiashvili, Felix Hommelsheim, Moritz Mühlenthaler, and Oliver Schaudt. Fault-Tolerant Edge-Disjoint s-t Paths - Beyond Uniform Faults. In Proceedings of the 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), volume 227, pages 5:1-5:19, 2022. URL: https://doi.org/10.4230/LIPIcs.SWAT.2022.5.
  2. Matthias Bentert, André Nichterlein, Malte Renken, and Philipp Zschoche. Using a Geometric Lens to Find k Disjoint Shortest Paths. In Proceedings of the 48th International Colloquium on Automata, Languages, and Programming (ICALP), volume 198, pages 26:1-26:14, 2021. URL: https://doi.org/10.4230/LIPIcs.ICALP.2021.26.
  3. Andreas Björklund, Thore Husfeldt, and Nina Taslaman. Shortest Cycle Through Specified Elements. In Proceedings of the 23rd Symposium on Discrete Algorithms (SODA), pages 1747-1753, 2012. URL: https://doi.org/10.1137/1.9781611973099.139.
  4. Glencora Borradaile and Philip Klein. The Two-Edge Connectivity Survivable-Network Design Problem in Planar Graphs. ACM Transactions on Algorithms, 12(3):30:1-30:29, 2016. URL: https://doi.org/10.1145/2831235.
  5. Jaroslaw Byrka, Fabrizio Grandoni, Thomas Rothvoß, and Laura Sanita. An Improved LP-based Approximation for Steiner Tree. In Proceedings of the 42nd Symposium on Theory of Computing, pages 583-592, 2010. URL: https://doi.org/10.1145/1806689.1806769.
  6. Artur Czumaj and Andrzej Lingas. On Approximability of the Minimum-Cost k-Connected Spanning Subgraph Problem. In Proceedings of the 10th Symposium on Discrete Algorithms (SODA), pages 281-290, 1999. URL: https://dl.acm.org/doi/pdf/10.5555/314500.314573.
  7. Nathaniel Dean. Open Problems. In Neil Robertson and Paul D. Seymour, editors, Graph Structure Theory, Proceedings of a AMS-IMS-SIAM Joint Summer Research Conference on Graph Minors, volume 147 of Contemporary Mathematics, pages 677-688. American Mathematical Society, 1991. Google Scholar
  8. Reinhard Diestel. Graph Theory. Graduate Texts in Mathematics. Springer, 2017. URL: https://doi.org/10.1007/978-3-662-53622-3.
  9. 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.
  10. Stefan Fafianie and Stefan Kratsch. An Experimental Analysis of a Polynomial Compression for the Steiner Cycle Problem. In Proceedings of the 14th International Symposium on Experimental Algorithms (SEA), volume 9125 of Lecture Notes in Computer Science, pages 367-378, 2015. URL: https://doi.org/10.1007/978-3-319-20086-6_28.
  11. Andreas Emil Feldmann, Anish Mukherjee, and Erik Jan van Leeuwen. The Parameterized Complexity of the Survivable Network Design Problem. In Proceedings of the 5th Symposium on Simplicity in Algorithms (SOSA), pages 37-56, 2022. URL: https://doi.org/10.1137/1.9781611977066.4.
  12. Lisa Fleischer, Kamal Jain, and David P. Williamson. Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems. Journal of Computer and System Sciences, 72(5):838-867, 2006. URL: https://doi.org/10.1016/j.jcss.2005.05.006.
  13. Herbert Fleischner and Gerhard J. Woeginger. Detecting cycles through three fixed vertices in a graph. Information Processing Letters, 42(1):29-33, 1992. URL: https://doi.org/10.1016/0020-0190(92)90128-I.
  14. Dorit S. Hochbaum and David B. Shmoys. A Unified Approach to Approximation Algorithms for Bottleneck Problems. Journal of the ACM, 33(3):533-550, 1986. URL: https://doi.org/10.1145/5925.5933.
  15. Oscar H. Ibarra and Chul E. Kim. Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems. Journal of the ACM, 22(4):463-468, 1975. URL: https://doi.org/10.1145/321906.321909.
  16. Kamal Jain. A Factor 2 Approximation Algorithm for the Generalized Steiner Network Problem. Combinatorica, 21(1):39-60, 2001. URL: https://doi.org/10.1007/s004930170004.
  17. Tibor Jordán. On minimally k-edge-connected graphs and shortest k-edge-connected Steiner networks. Discrete Applied Mathematics, 131(2):421-432, 2003. URL: https://doi.org/10.1016/S0166-218X(02)00465-1.
  18. Richard M Karp. On the Computational Complexity of Combinatorial Problems. Networks, 5(1):45-68, 1975. URL: https://doi.org/10.1002/net.1975.5.1.45.
  19. Ken-ichi Kawarabayashi. An Improved Algorithm for Finding Cycles Through Elements. In Proceedings of the 13th Integer Programming and Combinatorial Optimization (IPCO), volume 5035, pages 374-384. Springer, 2008. URL: https://doi.org/10.1007/978-3-540-68891-4_26.
  20. Samir Khuller and Uzi Vishkin. Biconnectivity Approximations and Graph Carvings. Journal of the ACM, 41(2):214-235, 1994. URL: https://doi.org/10.1145/174652.174654.
  21. William Lochet. A Polynomial Time Algorithm for the k-Disjoint Shortest Paths Problem. In Proceedings of the 32nd Symposium on Discrete Algorithms (SODA), pages 169-178, 2021. URL: https://doi.org/10.1137/1.9781611976465.12.
  22. Zeev Nutov. Node-Connectivity Survivable Network Problems. In Teofilo F. Gonzalez, editor, Handbook of Approximation Algorithms and Metaheuristics, Second Edition, Volume 2: Contemporary and Emerging Applications. Chapman and Hall/CRC, 2018. Google Scholar
  23. Neil Robertson and Paul D Seymour. Graph Minors. XIII. The Disjoint Paths Problem. Journal of Combinatorial Theory, Series B, 63(1):65-110, 1995. URL: https://doi.org/10.1006/jctb.1995.1006.
  24. Sasha Sami. Parameterized Algorithms for 2-Edge Connected Steiner Subgraphs. Univerzita Karlova, Matematicko-fyzikální fakulta, 2023. URL: https://dspace.cuni.cz/handle/20.500.11956/179482.
  25. Alexander Schrijver. Combinatorial Optimization: Polyhedra and Efficiency, volume 24 of Algorithms and Combinatorics. Springer, 2003. Google Scholar
  26. Nina Taslaman. Exponential-Time Algorithms and Complexity of NP-Hard Graph Problems. Number 83 in ITU-DS. IT-Universitetet i København, 2013. URL: https://pure.itu.dk/ws/portalfiles/portal/39516792/nina_thesis.pdf.
  27. Magnus Wahlström. Abusing the Tutte Matrix: An Algebraic Instance Compression for the K-set-cycle Problem. In Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science (STACS), volume 20, pages 341-352, 2013. URL: https://doi.org/10.4230/LIPIcs.STACS.2013.341.
  28. Hassler Whitney. Non-Separable and Planar Graphs. Transactions of the American Mathematical Society, 34:339-362, 1932. URL: https://doi.org/10.1090/S0002-9947-1932-1501641-2.
  29. David P. Williamson and David B. Shmoys. The Design of Approximation Algorithms. Cambridge University Press, 2011. URL: http://www.cambridge.org/knowledge/isbn/item5759340/.
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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