Approximation Algorithms for Relative Survivable Network Design Problems

Abstract 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 2^O (k²) -approximation for with a single demand of k.