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

• Published in: Journal of Quaternary Science
• Main Authors: Adjiashvili, David, Hommelsheim, Felix, Mühlenthaler, Moritz, Schaudt, Oliver
• Other Authors: Department of Mathematics - ETH, Eidgenössische Technische Hochschule - Swiss Federal Institute of Technology Zürich (ETH Zürich), Faculty of Computer Science and Mathematics Bremen, University of Bremen, Optimisation Combinatoire (G-SCOP_OC), Laboratoire des sciences pour la conception, l'optimisation et la production (G-SCOP), Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA), Institut fur Mathematik, RWTH Aachen Univers
• Format: Conference Object
• Language: English
• Published: HAL CCSD 2022
• Subjects: network design; fault tolerance; approximation algorithms; graph algorithms; [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]; Faroe Islands; Torshavn
• Online Access: https://hal.science/hal-04214508; https://hal.science/hal-04214508/document; https://hal.science/hal-04214508/file/LIPIcs-SWAT-2022-5.pdf; https://doi.org/10.4230/LIPIcs.SWAT.2022.5

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.