Document Open Access Logo

A Parameterized Algorithm for Vertex Connectivity Survivable Network Design Problem with Uniform Demands

Authors Jørgen Bang-Jensen , Kristine Vitting Klinkby, Pranabendu Misra , Saket Saurabh

PDF
Thumbnail PDF

File

LIPIcs.ESA.2023.13.pdf
  • Filesize: 0.84 MB
  • 15 pages

Document Identifiers

Author Details

Jørgen Bang-Jensen
  • University of Southern Denmark, Odense, Denmark
Kristine Vitting Klinkby
  • University of Southern Denmark, Odense, Denmark
Pranabendu Misra
  • Chennai Mathematical Institute, India
Saket Saurabh
  • Institute of Mathematical Sciences, Chennai, India
  • University of Bergen, Norway

Funding

  • Misra, Pranabendu: Supported by Google India Research Award 2022, and Start-Up Grant 2022 (SRG/2022/001927) of Science and Engineering Research Board (SERB), India.
  • Saurabh, Saket: Supported by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No. 819416), and Swarnajayanti Fellowship (No. DST/SJF/MSA01/2017-18).

Cite AsGet BibTex

Jørgen Bang-Jensen, Kristine Vitting Klinkby, Pranabendu Misra, and Saket Saurabh. A Parameterized Algorithm for Vertex Connectivity Survivable Network Design Problem with Uniform Demands. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 13:1-13:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.ESA.2023.13

Abstract

In the Vertex Connectivity Survivable Network Design (VC-SNDP) problem, the input is a graph G and a function d: V(G) × V(G) → ℕ that encodes the vertex-connectivity demands between pairs of vertices. The objective is to find the smallest subgraph H of G that satisfies all these demands. It is a well-studied NP-complete problem that generalizes several network design problems. We consider the case of uniform demands, where for every vertex pair (u,v) the connectivity demand d(u,v) is a fixed integer κ. It is an important problem with wide applications. We study this problem in the realm of Parameterized Complexity. In this setting, in addition to G and d we are given an integer 𝓁 as the parameter and the objective is to determine if we can remove at least 𝓁 edges from G without violating any connectivity constraints. This was posed as an open problem by Bang-Jansen et.al. [SODA 2018], who studied the edge-connectivity variant of the problem under the same settings. Using a powerful classification result of Lokshtanov et al. [ICALP 2018], Gutin et al. [JCSS 2019] recently showed that this problem admits a (non-uniform) FPT algorithm where the running time was unspecified. Further they also gave an (uniform) FPT algorithm for the case of κ = 2. In this paper we present a (uniform) FPT algorithm any κ that runs in time 2^{O(κ² 𝓁⁴ log 𝓁)}⋅ |V(G)|^O(1). Our algorithm is built upon new insights on vertex connectivity in graphs. Our main conceptual contribution is a novel graph decomposition called the Wheel decomposition. Informally, it is a partition of the edge set of a graph G, E(G) = X₁ ∪ X₂ … ∪ X_r, with the parts arranged in a cyclic order, such that each vertex v ∈ V(G) either has edges in at most two consecutive parts, or has edges in every part of this partition. The first kind of vertices can be thought of as the rim of the wheel, while the second kind form the hub. Additionally, the vertex cuts induced by these edge-sets in G have highly symmetric properties. Our main technical result, informally speaking, establishes that "nearly edge-minimal’’ κ-vertex connected graphs admit a wheel decomposition - a fact that can be exploited for designing algorithms. We believe that this decomposition is of independent interest and it could be a useful tool in resolving other open problems.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
Keywords
  • Parameterized Complexity
  • Vertex Connectivity
  • Network Design

Metrics

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

References

  1. Jørgen Bang-Jensen, Manu Basavaraju, Kristine Vitting Klinkby, Pranabendu Misra, MS Ramanujan, Saket Saurabh, and Meirav Zehavi. Parameterized algorithms for survivable network design with uniform demands. In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2838-2850. SIAM, 2018. Google Scholar
  2. Jørgen Bang-Jensen and Anders Yeo. The minimum spanning strong subdigraph problem is fixed parameter tractable. Discrete Applied Mathematics, 156(15):2924-2929, 2008. Google Scholar
  3. Jørgen Bang-Jensen and Gregory Gutin. Digraphs. Theory, Algorithms and Applications. Springer, 2002. Google Scholar
  4. Manu Basavaraju, Fedor V Fomin, Petr Golovach, Pranabendu Misra, MS Ramanujan, and Saket Saurabh. Parameterized algorithms to preserve connectivity. In Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP), pages 800-811. Springer, 2014. Google Scholar
  5. Jaroslaw Byrka, Fabrizio Grandoni, and Afrouz Jabal Ameli. Breaching the 2-approximation barrier for connectivity augmentation: a reduction to steiner tree. In Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy, editors, Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020, pages 815-825. ACM, 2020. URL: https://doi.org/10.1145/3357713.3384301.
  6. Tanmoy Chakraborty, Julia Chuzhoy, and Sanjeev Khanna. Network design for vertex connectivity. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC), pages 167-176, 2008. Google Scholar
  7. Joseph Cheriyan and László A Végh. Approximating minimum-cost k-node connected subgraphs via independence-free graphs. SIAM Journal on Computing, 43(4):1342-1362, 2014. Google Scholar
  8. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer Science & Business Media, 2015. Google Scholar
  9. Andreas Emil Feldmann, Anish Mukherjee, and Erik Jan van Leeuwen. The parameterized complexity of the survivable network design problem. In Symposium on Simplicity in Algorithms (SOSA), pages 37-56. SIAM, 2022. Google Scholar
  10. Fedor V. Fomin, Petr A. Golovach, William Lochet, Pranabendu Misra, Saket Saurabh, and Roohani Sharma. Parameterized complexity of directed spanner problems. In Yixin Cao and Marcin Pilipczuk, editors, 15th International Symposium on Parameterized and Exact Computation, IPEC 2020, December 14-18, 2020, Hong Kong, China (Virtual Conference), volume 180 of LIPIcs, pages 12:1-12:11. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.IPEC.2020.12.
  11. Greg N Frederickson and Joseph Ja'Ja'. Approximation algorithms for several graph augmentation problems. SIAM Journal on Computing, 10(2):270-283, 1981. Google Scholar
  12. Gregory Gutin, M.S. Ramanujan, Felix Reidl, and Magnus Wahlström. Path-contractions, edge deletions and connectivity preservation. Journal of Computer and System Sciences, 101:1-20, 2019. URL: https://doi.org/10.1016/j.jcss.2018.10.001.
  13. Kamal Jain. A factor 2 approximation algorithm for the generalized steiner network problem. Combinatorica, 21(1):39-60, 2001. Google Scholar
  14. Samir Khuller. Approximation algorithms for finding highly connected subgraphs. In Approximation algorithms for NP-hard problems, pages 236-265. PWS Publishing Co., 1996. Google Scholar
  15. Kristine Vitting Klinkby, Pranabendu Misra, and Saket Saurabh. Strong connectivity augmentation is FPT. In Dániel Marx, editor, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021, pages 219-234. SIAM, 2021. URL: https://doi.org/10.1137/1.9781611976465.15.
  16. Yusuke Kobayashi. Np-hardness and fixed-parameter tractability of the minimum spanner problem. Theor. Comput. Sci., 746:88-97, 2018. URL: https://doi.org/10.1016/j.tcs.2018.06.031.
  17. Yusuke Kobayashi. An FPT algorithm for minimum additive spanner problem. In Christophe Paul and Markus Bläser, editors, 37th International Symposium on Theoretical Aspects of Computer Science, STACS 2020, March 10-13, 2020, Montpellier, France, volume 154 of LIPIcs, pages 11:1-11:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.STACS.2020.11.
  18. Guy Kortsarz, Robert Krauthgamer, and James R. Lee. Hardness of approximation for vertex-connectivity network design problems. SIAM Journal on Computing, 33(3):704-720, 2004. URL: https://doi.org/10.1137/S0097539702416736.
  19. Guy Kortsarz and Zeev Nutov. Approximating minimum cost connectivity problems. In Dagstuhl Seminar Proceedings. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2010. Google Scholar
  20. Daniel Lokshtanov, M. S. Ramanujan, Saket Saurabh, and Meirav Zehavi. Reducing CMSO model checking to highly connected graphs. In Ioannis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, and Donald Sannella, editors, 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic, volume 107 of LIPIcs, pages 135:1-135:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.ICALP.2018.135.
  21. Dániel Marx and László A Végh. Fixed-parameter algorithms for minimum-cost edge-connectivity augmentation. ACM Transactions on Algorithms (TALG), 11(4):27, 2015. Google Scholar
  22. Zeev Nutov. Approximability status of survivable network problems, 2014. Google Scholar
  23. Zeev Nutov. Approximating minimum-cost edge-covers of crossing biset-families. Combinatorica, 34(1):95-114, 2014. Google Scholar
  24. Vera Traub and Rico Zenklusen. A better-than-2 approximation for weighted tree augmentation. CoRR, abs/2104.07114, 2021. URL: https://arxiv.org/abs/2104.07114.
  25. Vera Traub and Rico Zenklusen. A (1.5+ε)-approximation algorithm for weighted connectivity augmentation. arXiv preprint arXiv:2209.07860, 2022. Google Scholar
  26. László A Végh. Augmenting undirected node-connectivity by one. SIAM Journal on Discrete Mathematics, 25(2):695-718, 2011. 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 Imprint Privacy Contact