2023/04/13 by Michael Dinitz, Ama Koranteng, Dinitz, Michael +5 · 1 citation
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Interconnection Networks and Systems
paper · pdf · doi:10.48550/arxiv.2304.06656
openalex publication_date 2023/04/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
One of the most important and well-studied settings for network design is edge-connectivity requirements. This encompasses uniform demands such as the Minimum k-Edge-Connected Spanning Subgraph problem as well as nonuniform demands such as the Survivable Network Design problem (SND). In a recent paper by [Dinitz, Koranteng, Kortsarz APPROX '22] , the authors observed that a weakness of these formulations is that it does not enable one to consider fault-tolerance in graphs that have just a few small cuts. To remedy this, they introduced new variants of these problems under the notion "relative" fault-tolerance. Informally, this requires not that two nodes are connected if there are a bounded number of faults (as in the classical setting), but that two nodes are connected if there are a bounded number of faults and the two nodes are connected in the underlying graph post-faults. The problem is already highly non-trivial even for the case of a single demand. Due to difficulties introduced by this new notion of fault-tolerance, the results in [Dinitz, Koranteng, Kortsarz APPROX '22] are quite limited. For the Relative Survivable Network Design problem (RSND), when the demands are not uniform they give a nontrivial result only when there is a single demand with a connectivity requirement of 3: a non-optimal 27/4-approximation. We strengthen this result in two significant ways: We give a 2-approximation for RSND where all requirements are at most 3, and a 2O(k2)-approximation for RSND with a single demand of arbitrary value k. To achieve these results, we first use the "cactus representation'' of minimum cuts to give a lossless reduction to normal SND. Second, we extend the techniques of [Dinitz, Koranteng, Kortsarz APPROX '22] to prove a generalized and more complex version of their structure theorem, which we then use to design a recursive approximation algorithm.