Document Open Access Logo

Relative Survivable Network Design

Authors Michael Dinitz, Ama Koranteng, Guy Kortsarz

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2022.41.pdf
  • Filesize: 0.67 MB
  • 19 pages

Document Identifiers

Author Details

Michael Dinitz
  • Johns Hopkins University, Baltimore, MD, USA
Ama Koranteng
  • Johns Hopkins University, Baltimore, MD, USA
Guy Kortsarz
  • Rutgers University, Camden, NJ, USA

Funding

  • Dinitz, Michael: Supported in part by NSF award CCF-1909111.
  • Koranteng, Ama: Supported in part by NSF award CCF-1909111.

Cite As Get BibTex

Michael Dinitz, Ama Koranteng, and Guy Kortsarz. Relative Survivable Network Design. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 41:1-41:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2022.41

Abstract

One of the most important and well-studied settings for network design is edge-connectivity requirements. This encompasses uniform demands such as the Minimum k-Edge-Connected Spanning Subgraph problem (k-ECSS), as well as nonuniform demands such as the Survivable Network Design problem. A weakness of these formulations, though, is that we are not able to ask for fault-tolerance larger than the connectivity. Taking inspiration from recent definitions and progress in graph spanners, we introduce and study new variants of these problems under a notion of relative fault-tolerance. Informally, we require not that two nodes are connected if there are a bounded number of faults (as in the classical setting), but that two nodes are connected if there are a bounded number of faults and the two nodes are connected in the underlying graph post-faults. That is, the subgraph we build must "behave" identically to the underlying graph with respect to connectivity after bounded faults. 
We define and introduce these problems, and provide the first approximation algorithms: a (1+4/k)-approximation for the unweighted relative version of k-ECSS, a 2-approximation for the weighted relative version of k-ECSS, and a 27/4-approximation for the special case of Relative Survivable Network Design with only a single demand with a connectivity requirement of 3. To obtain these results, we introduce a number of technical ideas that may of independent interest. First, we give a generalization of Jain’s iterative rounding analysis that works even when the cut-requirement function is not weakly supermodular, but instead satisfies a weaker definition we introduce and term local weak supermodularity. Second, we prove a structure theorem and design an approximation algorithm utilizing a new decomposition based on important separators, which are structures commonly used in fixed-parameter algorithms that have not commonly been used in approximation algorithms.

Subject Classification

ACM Subject Classification
  • Theory of computation → Routing and network design problems
Keywords
  • Fault Tolerance
  • Network Design

Metrics

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

Related Versions

References

  1. Ajit Agrawal, Philip Klein, and R. Ravi. When trees collide: an approximation algorithm for the generalized Steiner problem on networks. SIAM J. Comput., 24(3):440-456, 1995. URL: https://doi.org/10.1137/S0097539792236237.
  2. Surender Baswana, Keerti Choudhary, and Liam Roditty. Fault tolerant subgraph for single source reachability: Generic and optimal. In Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing, STOC '16, pages 509-518, New York, NY, USA, 2016. Association for Computing Machinery. URL: https://doi.org/10.1145/2897518.2897648.
  3. Greg Bodwin, Michael Dinitz, and Yasamin Nazari. Vertex fault-tolerant emulators. In Mark Braverman, editor, 13th Innovations in Theoretical Computer Science Conference, ITCS 2022, volume 215 of LIPIcs, pages 25:1-25:22. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. URL: https://doi.org/10.4230/LIPIcs.ITCS.2022.25.
  4. Greg Bodwin, Michael Dinitz, Merav Parter, and Virginia Vassilevska Williams. Optimal vertex fault tolerant spanners (for fixed stretch). In Artur Czumaj, editor, Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 1884-1900. SIAM, 2018. Google Scholar
  5. Greg Bodwin, Michael Dinitz, and Caleb Robelle. Optimal vertex fault-tolerant spanners in polynomial time. In Proceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, 2021. Google Scholar
  6. Greg Bodwin, Michael Dinitz, and Caleb Robelle. Optimal vertex fault-tolerant spanners in polynomial time. In Joseph (Seffi) Naor and Niv Buchbinder, editors, Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, pages 2924-2938. SIAM, 2022. URL: https://doi.org/10.1137/1.9781611976465.174.
  7. Greg Bodwin and Shyamal Patel. A trivial yet optimal solution to vertex fault tolerant spanners. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC ’19, pages 541-543, New York, NY, USA, 2019. Association for Computing Machinery. URL: https://doi.org/10.1145/3293611.3331588.
  8. Shiri Chechik, Michael Langberg, David Peleg, and Liam Roditty. f-sensitivity distance oracles and routing schemes. In Mark de Berg and Ulrich Meyer, editors, Algorithms - ESA 2010, pages 84-96, Berlin, Heidelberg, 2010. Springer Berlin Heidelberg. Google Scholar
  9. Shiri Chechik, Michael Langberg, David Peleg, and Liam Roditty. Fault tolerant spanners for general graphs. SIAM J. Comput., 39(7):3403-3423, 2010. Google Scholar
  10. Joseph Cheriyan and Ramakrishna Thurimella. Approximating minimum-size k-connected spanning subgraphs via matching. SIAM Journal on Computing, 30(2):528-560, 2000. URL: https://doi.org/10.1137/S009753979833920X.
  11. Julia Chuzhoy and Sanjeev Khanna. An o(k³ log n)-approximation algorithm for vertex-connectivity survivable network design. Theory Comput., 8(1):401-413, 2012. URL: https://doi.org/10.4086/toc.2012.v008a018.
  12. Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein. Introduction to algorithms. MIT press, 2022. Google Scholar
  13. Michael Dinitz, Ama Koranteng, and Guy Kortsarz. Relative survivable network design, 2022. URL: https://doi.org/10.48550/ARXIV.2206.12245.
  14. Michael Dinitz and Robert Krauthgamer. Fault-tolerant spanners: better and simpler. In Proceedings of the 30th Annual ACM Symposium on Principles of Distributed Computing, PODC 2011, San Jose, CA, USA, June 6-8, 2011, pages 169-178, 2011. Google Scholar
  15. Michael Dinitz and Caleb Robelle. Efficient and simple algorithms for fault-tolerant spanners. In Yuval Emek and Christian Cachin, editors, PODC '20: ACM Symposium on Principles of Distributed Computing, pages 493-500. ACM, 2020. URL: https://doi.org/10.1145/3382734.3405735.
  16. Harold N. Gabow and Suzanne R. Gallagher. Iterated rounding algorithms for the smallest k-edge connected spanning subgraph. SIAM Journal on Computing, 41(1):61-103, 2012. URL: https://doi.org/10.1137/080732572.
  17. Harold N. Gabow, Michel X. Goemans, Éva Tardos, and David P. Williamson. Approximating the smallest k-edge connected spanning subgraph by lp-rounding. Networks, 53(4):345-357, 2009. Google Scholar
  18. Martin Grötschel, László Lovász, and Alexander Schrijver. Geometric Algorithms and Combinatorial Optimization, volume 2 of Algorithms and Combinatorics. Springer, 1988. URL: https://doi.org/10.1007/978-3-642-97881-4.
  19. 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.
  20. Lap-Chi Lau, R. Ravi, and Mohit Singh. Iterative Methods in Combinatorial Optimization. Cambridge University Press, USA, 1st edition, 2011. Google Scholar
  21. Daniel Lokshtanov, Pranabendu Misra, Saket Saurabh, and Meirav Zehavi. A brief note on single source fault tolerant reachability, 2019. URL: https://doi.org/10.48550/ARXIV.1904.08150.
  22. Dániel Marx. Important separators and parameterized algorithms. In International Workshop on Graph-Theoretic Concepts in Computer Science, pages 5-10. Springer, 2011. Google Scholar
  23. K. Steiglitz, P. Weiner, and D. Kleitman. The design of minimum-cost survivable networks. IEEE Transactions on Circuit Theory, 16(4):455-460, 1969. URL: https://doi.org/10.1109/TCT.1969.1083004.
  24. David P. Williamson, Michel X. Goemans, Milena Mihail, and Vijay V. Vazirani. A primal-dual approximation algorithm for generalized steiner network problems. Combinatorica, 15(3):435-454, 1995. URL: https://doi.org/10.1007/BF01299747.
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