Document Open Access Logo

Fault-Tolerant Edge-Disjoint s-t Paths - Beyond Uniform Faults

Authors David Adjiashvili, Felix Hommelsheim , Moritz Mühlenthaler , Oliver Schaudt

PDF
Thumbnail PDF

File

LIPIcs.SWAT.2022.5.pdf
  • Filesize: 0.78 MB
  • 19 pages

Document Identifiers

Author Details

David Adjiashvili
  • Department of Mathematics, ETH Zürich, Switzerland
Felix Hommelsheim
  • Department of Mathematics and Computer Science, Universität Bremen, Germany
Moritz Mühlenthaler
  • Laboratoire G-SCOP, Grenoble INP, Univ. Grenoble-Alpes, France
Oliver Schaudt
  • Department of Mathematics, RWTH Aachen University, Germany

Cite As Get BibTex

David Adjiashvili, Felix Hommelsheim, Moritz Mühlenthaler, and Oliver Schaudt. Fault-Tolerant Edge-Disjoint s-t Paths - Beyond Uniform Faults. In 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 227, pp. 5:1-5:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.SWAT.2022.5

Abstract

The Edge-disjoint s-t Paths Problem (s-t EDP) is a classical network design problem whose goal is to connect for some k ≥ 1 two given vertices of a graph under the condition that any k-1 edges of the graph may fail. We extend the simple uniform failure model of the s-t EDP as follows: the edge set of the graph is partitioned into vulnerable, and safe edges, and a set of at most k vulnerable edges may fail, while safe edges do not fail. In particular we study the Fault-Tolerant Path (FTP) problem, the counterpart of the Shortest s-t Path problem in this non-uniform failure model as well as the Fault-Tolerant Flow (FTF) problem, the counterpart of s-t EDP. We present complexity results alongside exact and approximation algorithms for both problems. We emphasize the vast increase in complexity of the problems compared to s-t EDP.

Subject Classification

ACM Subject Classification
  • Theory of computation → Routing and network design problems
  • Theory of computation → Network flows
  • Mathematics of computing → Approximation algorithms
Keywords
  • graph algorithms
  • network design
  • fault tolerance
  • approximation algorithms

Metrics

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

Related Versions

References

  1. David Adjiashvili. Non-uniform robust network design in planar graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2015. Google Scholar
  2. David Adjiashvili, Felix Hommelsheim, and Moritz Mühlenthaler. Flexible graph connectivity. In International Conference on Integer Programming and Combinatorial Optimization, pages 13-26. Springer, 2020. Google Scholar
  3. David Adjiashvili, Sebastian Stiller, and Rico Zenklusen. Bulk-robust combinatorial optimization. Mathematical Programming, 149(1-2):361-390, 2015. URL: https://doi.org/10.1007/s10107-014-0760-6.
  4. Hassene Aissi, Cristina Bazgan, and Daniel Vanderpooten. Approximation complexity of min-max (regret) versions of shortest path, spanning tree, and knapsack. In European Symposium on Algorithms, pages 862-873. Springer, 2005. Google Scholar
  5. Sylvia Boyd, Joseph Cheriyan, Arash Haddadan, and Sharat Ibrahimpur. A 2-approximation algorithm for flexible graph connectivity. arXiv preprint, 2021. URL: http://arxiv.org/abs/2102.03304.
  6. Christina Büsing. Recoverable robust shortest path problems. Networks, 59(1):181-189, 2012. Google Scholar
  7. Deeparnab Chakrabarty, Chandra Chekuri, Sanjeev Khanna, and Nitish Korula. Approximability of capacitated network design. Algorithmica, 72(2):493-514, 2015. Google Scholar
  8. Moses Charikar, Chandra Chekuri, To-yat Cheung, Zuo Dai, Ashish Goel, Sudipto Guha, and Ming Li. Approximation algorithms for directed Steiner problems. Journal of Algorithms, 33(1):73-91, 1999. Google Scholar
  9. Joseph Cheriyan, Bundit Laekhanukit, Guyslain Naves, and Adrian Vetta. Approximating rooted steiner networks. ACM Transactions on Algorithms (TALG), 11(2):1-22, 2014. Google Scholar
  10. Kedar Dhamdhere, Vineet Goyal, R Ravi, and Mohit Singh. How to pay, come what may: Approximation algorithms for demand-robust covering problems. In 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05), pages 367-376. IEEE, 2005. Google Scholar
  11. Jon Feldman and Matthias Ruhl. The directed Steiner network problem is tractable for a constant number of terminals. SIAM Journal on Computing, 36(2):543-561, 2006. URL: https://doi.org/10.1137/S0097539704441241.
  12. 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. Google Scholar
  13. Daniel Golovin, Vineet Goyal, Valentin Polishchuk, R Ravi, and Mikko Sysikaski. Improved approximations for two-stage min-cut and shortest path problems under uncertainty. Mathematical Programming, 149(1-2):167-194, 2015. Google Scholar
  14. Jiong Guo, Rolf Niedermeier, and Ondřej Suchỳ. Parameterized complexity of arc-weighted directed Steiner problems. SIAM Journal on Discrete Mathematics, 25(2):583-599, 2011. Google Scholar
  15. Eran Halperin and Robert Krauthgamer. Polylogarithmic inapproximability. In Proceedings of the 35th Annual ACM Symposium on Theory of Computing, pages 585-594, 2003. URL: https://doi.org/10.1145/780542.780628.
  16. Felix Hommelsheim, Moritz Mühlenthaler, and Oliver Schaudt. How to secure matchings against edge failures. SIAM Journal on Discrete Mathematics, 35(3):2265-2292, 2021. Google Scholar
  17. 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.
  18. Alexander Schrijver. Combinatorial optimization: polyhedra and efficiency, volume 24. Springer Science & Business Media, 2003. Google Scholar
  19. Gang Yu and Jian Yang. On the robust shortest path problem. Computers and Operations Research, 25(6):457-468, June 1998. Google Scholar
  20. Paweł Zieliński. The computational complexity of the relative robust shortest path problem with interval data. European Journal of Operational Research, 158(3):570-576, November 2004. URL: https://doi.org/10.1016/s0377-2217(03)00373-4.
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