  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 $2^{O(k^2)}$-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.
