2013/01/26 by David Adjiashvili, Adjiashvili, David
Business, Management and Accounting · Computer Science · Decision Sciences · #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #F.5.1 #F.5.2 #F.5.3 #FOS: Computer and information sciences #FOS: Mathematics #Facility Location and Emergency Management #Optimization and Control (math.OC) #Risk and Portfolio Optimization
paper · pdf · doi:10.48550/arxiv.1301.6299
openalex publication_date 2013/01/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The overwhelming majority of survivable (fault-tolerant) network design models assume a uniform scenario set. Such a scenario set assumes that every subset of the network resources (edges or vertices) of a given cardinality k comprises a scenario. While this approach yields problems with clean combinatorial structure and good algorithms, it often fails to capture the true nature of the scenario set coming from applications. One natural refinement of the uniform model is obtained by partitioning the set of resources into faulty and secure resources. The scenario set contains every subset of at most k faulty resources. This work studies the Fault-Tolerant Path (FTP) problem, the counterpart of the Shortest Path problem in this failure model. We present complexity results alongside exact and approximation algorithms for FTP. We emphasize the vast increase in the complexity of the problem with respect to its uniform analogue, the Edge-Disjoint Paths problem.