Approximation Algorithms for Relative Survivable Network Design Problems

Abstract In the {\sc Survivable Network Design} ({\SND}) problem we seek a min-cost subgraph that satisfies pairwise edge-connectivity demands. This encompasses the {\sc $k$-Edge-Connected Spanning Subgraph} ({\kECSS}) problem (the case of uniform demands), and the case of a single demand is essentially the {\sc 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 \emph{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 \emph{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 {\sc Relative}{\kECSS} ({\RkECSS}), a $(1+4/k)$-approximation for unweighted {\RkECSS}, a $2$-approximation for {\sc Relative SND} with demands $\leq 3$ ({\RtSND}), and a $2^{O(k^2)}$-approximation for {\RSND} with a single demand of $k$.