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 (k-ECSS), as well as nonuniform demands such as the Survivable Network Design problem (SND). A weakness of these formulations, though, is that we are not able to ask for fault-tolerance larger than the connectivity. We introduce and 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 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.

We define and introduce these problems, and provide the first approximation algorithms: a (1+4/k)-approximation for the unweighted relative version of k-ECSS, a 2-approximation for the weighted relative version of k-ECSS, and a 2-approximation for the special case of relative SND where all demands are at most 3. For relative k-ECSS, we give a generalization of Jain’s iterative rounding analysis that works even when the cut-requirement function is not weakly supermodular. For relative SND with demands at most 3, we use the "cactus representation'' of minimum cuts to give a lossless reduction to normal SND.

This is joint work with Michael Dinitz, Guy Kortsarz, and Zeev Nutov