2026-07-22T14:20:39Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16165 2024-03-06T10:57:03Z ddc:004 open_access

Fault-Tolerant Edge-Disjoint s-t Paths - Beyond Uniform Faults Adjiashvili, David Hommelsheim, Felix Mühlenthaler, Moritz Schaudt, Oliver graph algorithms network design fault tolerance approximation algorithms 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik David Adjiashvili and Felix Hommelsheim and Moritz Mühlenthaler and Oliver Schaudt 2022 Is Part Of LIPIcs, Volume 227, 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SWAT.2022.5 urn:nbn:de:0030-drops-161659 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2022.5 eng https://creativecommons.org/licenses/by/4.0/legalcode