Adjiashvili, DavidDavidAdjiashviliHommelsheim, FelixFelixHommelsheimMühlenthaler, MoritzMoritzMühlenthalerSchaudt, OliverOliverSchaudt2025-09-152025-09-152022https://media.suub.uni-bremen.de/handle/elib/22315https://doi.org/10.26092/elib/4266The 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.enhttps://creativecommons.org/licenses/by/4.0/graph algorithmsnetwork designfault toleranceapproximation algorithms000 Informatik, Informationswissenschaft, allgemeine WerkeText::Konferenzveröffentlichung::Tagungsband::Konferenzbeitrag10.26092/elib/4266urn:nbn:de:gbv:46-elib223155