Approximation Algorithms for Relative Survivable Network Design Problems

In the { Survivable Network Design} ({}) problem we seek a min-cost subgraph that satisfies pairwise edge-connectivity demands. This encompasses the { k-Edge-Connected Spanning Subgraph} ({}) problem (the case of uniform demands), and the case of a single demand is essentially the { Min-cost k-Flow} problem with unit capacities. A weakness of these formulations is that we cannot ask for fault-tolerance larger than the connectivity. Inspired by recent definitions and progress in graph spanners, we study new variants of these problems under a notion of relative fault-tolerance. Informally, we require not that two nodes are connected if there are k faults (as in the classical setting), but that two nodes are connected if there are k faults and the two nodes are connected in the underlying graph post-faults. That is, the subgraph must ''behave'' identically to the underlying graph with respect to connectivity after k faults. We define and introduce these ''relative'' problems, and provide approximation algorithms: a $2$-approximation for { Relative}{} ({}), a $(1+4/k)$-approximation for unweighted {}, a $2$-approximation for { Relative SND} with demands ≤ 3 ({}), and a 2O(k²)-approximation for {} with a single demand of k.