Tight Guarantees for Cut-Relative Survivable Network Design via a Decomposition Technique

Kumar, Nikhil; Nan, J. J.; Swamy, Chaitanya

doi:10.4230/LIPIcs.ESA.2025.38

Tight Guarantees for Cut-Relative Survivable Network Design via a Decomposition Technique

Nikhil Kumar University of Waterloo, Canada J. J. Nan University of Waterloo, Canada Chaitanya Swamy

University of Waterloo, Canada

Abstract

In the classical survivable-network-design problem ( $\mathsf{SNDP}$ ), we are given an undirected graph $G=(V,E)$ , non-negative edge costs, and some $k$ tuples $(s_{i},t_{i},r_{i})$ , where $s_{i},t_{i}\in V$ and $r_{i}\in\mathbb{Z}_{+}$ . The objective is to find a minimum-cost subset $H\subseteq E$ such that each $s_{i}$ - $t_{i}$ pair remains connected even after the failure of any $r_{i}-1$ edges. It is well-known that $\mathsf{SNDP}$ can be equivalently modeled using a weakly-supermodular cut-requirement function $f$ , where the objective is to find the minimum-cost subset of edges that picks at least $f(S)$ edges across every cut $S\subseteq V$ .

Recently, motivated by fault-tolerance in graph spanners, Dinitz, Koranteng, and Kortsartz proposed a variant of $\mathsf{SNDP}$ that enforces a relative level of fault tolerance with respect to $G$ . Even if a feasible $\mathsf{SNDP}$ -solution may not exist due to $G$ lacking the required fault-tolerance, the goal is to find a solution $H$ that is at least as fault-tolerant as $G$ itself. They formalize the latter condition in terms of paths and fault-sets, which gives rise to path-relative $\mathsf{SNDP}$ (which they call relative $\mathsf{SNDP}$ ). Along these lines, we introduce a new model of relative network design, called cut-relative $\mathsf{SNDP}$ ( $\mathsf{CR}\text{-}\mathsf{SNDP}$ ), where the goal is to select a minimum-cost subset of edges that satisfies the given (weakly-supermodular) cut-requirement function to the maximum extent possible, i.e., by picking $\min\{f(S),|\delta_{G}(S)|\}$ edges across every cut $S\subseteq V$ .

Unlike $\mathsf{SNDP}$ , the cut-relative and path-relative versions of $\mathsf{SNDP}$ are not equivalent. The resulting cut-requirement function for $\mathsf{CR}\text{-}\mathsf{SNDP}$ (as also path-relative $\mathsf{SNDP}$ ) is not weakly supermodular, and extreme-point solutions to the natural LP-relaxation need not correspond to a laminar family of tight cut constraints. Consequently, standard techniques cannot be used directly to design approximation algorithms for this problem. We develop a novel decomposition technique to circumvent this difficulty and use it to give a tight $2$ -approximation algorithm for $\mathsf{CR}\text{-}\mathsf{SNDP}$ . We also show some new hardness results for these relative- $\mathsf{SNDP}$ problems.

Keywords and phrases:

Approximation algorithms, Network Design, Cut-requirement functions, Weak Supermodularity, Iterative rounding, LP rounding algorithms

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Approximation algorithms analysis ; Mathematics of computing

\rightarrow

Discrete optimization

Related Version:

Full Version: https://arxiv.org/abs/2507.04473

Funding:

Supported in part by NSERC grant 327620-09.

DOI:

10.4230/LIPIcs.ESA.2025.38

Event:

33rd Annual European Symposium on Algorithms (ESA 2025)

Editors:

Anne Benoit, Haim Kaplan, Sebastian Wild, and Grzegorz Herman

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

In the classical survivable-network-design problem ( $\mathsf{SNDP}$ ), we are given an undirected graph $G=(V,E)$ , non-negative edge costs $\{c_{e}\}_{e\in E}$ , and some $k$ source-sink pairs $s_{i},t_{i}\in V$ with requirements $r_{i}\in\mathbb{Z}_{+}$ , for $i=1,\ldots,k$ . The goal is to find a minimum-cost set $H\subseteq E$ of edges such that there are at least $r_{i}$ edge-disjoint $s_{i}$ - $t_{i}$ paths in $H$ , for all $i\in[k]$ . We overload notation and use $H$ to denote both the edge-set, and the corresponding subgraph of $G$ .

$\mathsf{SNDP}$ imposes an absolute level of fault-tolerance in a solution subgraph $H$ , by ensuring that for any bounded-size fault-set $F\subseteq E$ of edges that may fail, the graph $H-F$ retains some connectivity properties. More precisely, due to Menger’s theorem, or the max-flow min-cut theorem, the feasibility condition on $H$ can be stated equivalently as follows. For every $i\in[k]$ , and every fault-set $F\subseteq E$ with $|F|<r_{i}$ :

(S1)

(Path-version) there is an $s_{i}$ - $t_{i}$ path in $H-F$ ;
(S2)

(Cut-version) for every $s_{i}$ - $t_{i}$ cut $S\subseteq V$ (i.e., $|S\cap\{s_{i},t_{i}\}|=1$ ), we have $\delta_{H-F}(S)\neq\emptyset$ , where $\delta_{H-F}(S):=\delta(S)\cap(H-F)$ .

Recently, motivated by work on fault-tolerance in graph spanners, Dinitz, Koranteng, and Kortsartz [8], proposed a variant of $\mathsf{SNDP}$ that aims to impose a relative level of fault-tolerance with respect to the graph $G$ . The idea is that even if the $\mathsf{SNDP}$ instance in infeasible, because $G$ itself does not possess the required level of fault-tolerance, one should not have to completely abandon the goal of fault-tolerance: it is still meaningful and reasonable to seek a solution that is “as fault-tolerant as $G$ ”, and in this sense is fault-tolerant relative to $G$ .

To formalize this, it is useful to consider the definition of $\mathsf{SNDP}$ in terms of fault-sets. Roughly speaking, we would like to capture that $H$ is a feasible solution if

for every fault-set

F

(valid for

\mathsf{SNDP}

),

H-F

and

G-F

have similar connectivity.

(*)

To elaborate, in $\mathsf{SNDP}$ , if there is even one fault-set $F^{\prime}$ under which $G-F^{\prime}$ fails to have the required connectivity, i.e., $|F^{\prime}|<r_{i}$ and $F^{\prime}\supseteq\delta_{G}(S)$ for some $s_{i}$ - $t_{i}$ cut $S$ , then “all bets are off”; we declare that the instance in infeasible. But declaring infeasibility here feels unsatisfactory because we allow one specific “problematic” fault-set $F^{\prime}$ to block us from obtaining any kind of fault-tolerance. In contrast, (* ‣ 1) aims to provide a per-fault-set guarantee, by asking for a solution $H$ that functions as well as $G$ in terms of connectivity under the failure of any fault-set $F$ (considered for $\mathsf{SNDP}$ ). We can formalize “ $H-F$ and $G-F$ have similar connectivity” in two ways, via paths or cuts, and this gives rise to the following two problem definitions.

Definition 1.1.

Let $\bigl(G=(V,E),\{c_{e}\}_{e\in E},\{s_{i},t_{i},r_{i}\}_{i\in[k]}\bigr)$ be an $\mathsf{SNDP}$ instance.

(R1)

Path-relative $\mathsf{SNDP}$ : $H\subseteq E$ is a feasible solution if for every $i\in[k]$ and $F\subseteq E$ with $|F|<r_{i}$ , $G-F$ has an $s_{i}$ - $t_{i}$ path $\implies$ $H-F$ has an $s_{i}$ - $t_{i}$ path.
(R2)

Cut-relative $\mathsf{SNDP}$ ( $\mathsf{CR}\text{-}\mathsf{SNDP}$ ): $H\subseteq E$ is a feasible solution if for every $i\in[k]$ and $F\subseteq E$ with $|F|<r_{i}$ , for every $s_{i}$ - $t_{i}$ cut $S$ , $\delta_{G-F}(S)\neq\emptyset\ \implies\ \delta_{H-F}(S)\neq\emptyset$ .

The goal in both problems is to find a minimum-cost feasible solution.

Perhaps surprisingly, path-relative $\mathsf{SNDP}$ and cut-relative $\mathsf{SNDP}$ are not equivalent, even when the $\mathsf{SNDP}$ instance involves a single $s$ - $t$ pair. It is not hard to show that if $H$ is feasible for $\mathsf{CR}\text{-}\mathsf{SNDP}$ , it is also feasible for path-relative SNDP¹¹1Fix any $i\in[k]$ and $F\subseteq E$ with $|F|<r_{i}$ . If $G-F$ has an $s_{i}$ - $t_{i}$ path, then $\delta_{G-F}(S)\neq\emptyset$ for every $s_{i}$ - $t_{i}$ cut. So since $H$ is feasible for cut-relative $\mathsf{SNDP}$ , we have $\delta_{H-F}(S)\neq\emptyset$ for every $s_{i}$ - $t_{i}$ cut, which implies that $H-F$ has an $s_{i}$ - $t_{i}$ path. but the converse fails to hold; see Section 7 for an example.

Path-relative $\mathsf{SNDP}$ was defined by Dinitz et al. [8], who referred to this problem simply as relative $\mathsf{SNDP}$ . They considered (among other problems) the path-relative version of $k$ -edge connected subgraph ( $k\text{-}\mathsf{ECSS}$ ), which is the special case of $\mathsf{SNDP}$ where we have an $s_{i}$ - $t_{i}$ pair with $r_{i}=k$ for every pair of nodes. (In this case, the path-relative and cut-relative versions do turn out to be equivalent [8].) They called the resulting path-relative problem, $k$ -edge fault-tolerant subgraph ( $k\text{-}\mathsf{EFTS}$ ), and observed that the feasibility condition for $k\text{-}\mathsf{EFTS}$ can be equivalently stated as: $H$ is feasible iff $|\delta_{H}(S)|\geq g(S):=\min\bigl\{k,|\delta_{G}(S)|\bigr\}$ for all $S\subseteq V$ . The function $g:2^{V}\mapsto\mathbb{Z}$ is called a cut-requirement function, as it stipulates the (minimum) number of edges across any cut in any feasible solution. Cut-requirement functions constitute a very versatile framework for specifying network-design problems, where given a cut-requirement function $f:2^{V}\mapsto\mathbb{Z}$ , the corresponding $f$ -network-design problem ( ${f}\text{-}\mathsf{NDP}$ ), also called the $f$ -connectivity problem, is to find a minimum-cost set $H\subseteq E$ such that $|\delta_{H}(S)|\geq f(S)$ for all $S\subseteq V$ . For instance, it is easy to see that $\mathsf{SNDP}$ corresponds to ${f}\text{-}\mathsf{NDP}$ for the cut-requirement function $f^{\mathsf{SNDP}}$ , defined by $f^{\mathsf{SNDP}}(S):=\max\,\{r_{i}:|S\cap\{s_{i},t_{i}\}|=1\}$ (and $k\text{-}\mathsf{ECSS}$ is ${f^{k\text{-}\mathsf{ECSS}}}\text{-}\mathsf{NDP}$ where $f^{k\text{-}\mathsf{ECSS}}(S):=k$ for all $\emptyset\neq S\subsetneq V$ ); various other network-design problems, such as the $T$ -join problem, point-to-point connection problem etc., can be modeled using suitable cut-requirement functions (see, e.g., [10, 11]).

Cut-relative $\mathsf{SNDP}$ is a problem that we introduce in this paper. Its formulation in terms of cuts is the problem one obtains when we replace $f^{k\text{-}\mathsf{ECSS}}$ in the cut-based formulation of $k\text{-}\mathsf{EFTS}$ by the cut-requirement function $f^{\mathsf{SNDP}}$ for (general) $\mathsf{SNDP}$ : that is, (similar to $k\text{-}\mathsf{EFTS}$ ), we can say that $H\subseteq E$ is feasible for $\mathsf{CR}\text{-}\mathsf{SNDP}$ iff $|\delta_{H}(S)|\geq g^{\mathsf{CR}\text{-}\mathsf{SNDP}}(S):=\min\bigl\{f^{% \mathsf{SNDP}}(S),|\delta_{G}(S)|\bigr\}$ for all $S\subseteq V$ (we show this easy equivalence in Section 2); in other words, $\mathsf{CR}\text{-}\mathsf{SNDP}$ corresponds to ${g^{\mathsf{CR}\text{-}\mathsf{SNDP}}}\text{-}\mathsf{NDP}$ . To gain some intuition for cut-relative $\mathsf{SNDP}$ , and contrast it with path-relative $\mathsf{SNDP}$ , consider $\mathsf{SNDP}$ with a single $s$ - $t$ pair and requirement $r$ , for simplicity. A feasible solution $H$ to path-relative $\mathsf{SNDP}$ offers a per-fault-set guarantee as encapsulated by (R1). But, for a given fault-set $F$ with $|F|<r$ , we get a weak fault-tolerance guarantee in terms of $s$ - $t$ cuts: if $\delta_{G-F}(S)=\emptyset$ for even one $s$ - $t$ cut $S$ then there is no requirement on $H$ for this fault-set $F$ . Cut-relative $\mathsf{SNDP}$ offers a per-fault-set and per-cut guarantee, since for (every $F$ with $|F|<r$ and) every $s$ - $t$ cut $S$ , we require that $\delta_{H-F}(S)\neq\emptyset$ if $\delta_{G-F}(S)\neq\emptyset$ .

Along the lines of $\mathsf{CR}\text{-}\mathsf{SNDP}$ , we can easily extend the cut-relative model to capture, more broadly, the cut-relative version of any network-design problem specified by a cut-requirement function: given a cut-requirement function $f$ , in the corresponding cut-relative $f$ -network-design problem ( $\mathsf{CR}\text{-}{f}\text{-}\mathsf{NDP}$ ), we seek a min-cost $H\subseteq E$ such that $|\delta_{H}(S)|\geq g^{\mathsf{CR}\text{-}{f}\text{-}\mathsf{NDP}}(S):=\min% \bigl\{f(S),|\delta_{G}(S)|\bigr\}$ for all $S\subseteq V$ ; that is, we seek to satisfy the cut-requirement function $f$ to the maximum extent possible. We refer to $f$ as the base cut-requirement function, to distinguish it from the cut-requirement function $g^{\mathsf{CR}\text{-}{f}\text{-}\mathsf{NDP}}$ that defines $\mathsf{CR}\text{-}{f}\text{-}\mathsf{NDP}$ .

Modeling power.

We arrived at $\mathsf{CR}\text{-}{f}\text{-}\mathsf{NDP}$ , which can be seen as a fault-tolerant cut-covering problem, as a technically natural extension of $k\text{-}\mathsf{EFTS}$ . We show below that $\mathsf{CR}\text{-}{f}\text{-}\mathsf{NDP}$ offers a surprising amount of modeling power, and, in particular, allows one to capture stronger forms of relative fault-tolerance compared to $k\text{-}\mathsf{EFTS}$ . In $k\text{-}\mathsf{EFTS}$ , there is a sharp relative-fault-tolerance threshold at $k$ : if $H$ is feasible, then $G-F$ and $H-F$ have the same components whenever $|F|<k$ , but there are no guarantees for larger fault-sets. With $\mathsf{CR}\text{-}{f}\text{-}\mathsf{NDP}$ , one can capture a weaker guarantee also for other fault-sets, which allows for a more graceful degradation of relative fault-tolerance as $|F|$ increases.

Example 1.2.

One way of modeling graceful relative-fault-tolerance degradation is as follows: given a non-increasing function $\tau:\mathbb{Z}_{+}\mapsto\mathbb{Z}_{+}$ , we seek a min-cost subgraph $H$ such that for every fault-set $F$ , $G-F$ and $H-F$ have exactly the same components with at most $\tau(|F|)$ nodes. If $G$ models a communication network where connected nodes can communicate with each other, then this yields the desirable guarantee that, post-faults, if a node can communicate with more than $\tau(|F|)$ nodes in $G$ then the same holds for $H$ ; if this number is at most $\tau(|F|)$ , then post-faults, it can communicate with the same nodes in $G$ and $H$ . Note that if $\tau(k-1)\geq n=|V|$ , then $H$ is feasible for $k\text{-}\mathsf{EFTS}$ ; by adding more “levels” to $\tau$ , we can obtain fault-tolerance guarantees for larger fault-sets.

In Section 3, we show that this problem can be modeled as $\mathsf{CR}\text{-}{f}\text{-}\mathsf{NDP}$ with the weakly-supermodular function $f=f^{\mathsf{grace}}$ , where $f^{\mathsf{grace}}(S):=\min\,\{\ell:\tau(\ell)<|S|\}$ , for $S\neq\emptyset$ .

Example 1.3.

Generalizing Example 1.2 substantially, suppose along with $\tau$ , we have a monotone function $\pi:2^{V}\mapsto\mathbb{R}_{+}$ , i.e., $\pi(T)\leq\pi(S)$ if $T\subseteq S$ . We now seek a subgraph $H$ such that for every fault-set $F$ and $S\subseteq V$ with $\pi(S)\leq\tau(|F|)$ , we have that $S$ is (the node-set of) a component of $G-F$ iff it is a component of $H-F$ . Similar to Example 1.2, we can model this as $\mathsf{CR}\text{-}{f}\text{-}\mathsf{NDP}$ by defining $f(S):=\min\,\{\ell:\tau(\ell)<\pi(S)\}$ , for $S\neq\emptyset$ (Theorem 3.2).

This setup yields fault-tolerance degradation depending on monotone properties of components other than just their size, which creates a rich space of problems. For example, suppose $\pi(S)=\max_{u,v\in S}\min_{\text{$u$-$v$ paths $P$ in $G$}}|P|$ is the weak-diameter of $S$ . Setting $\tau(\ell)=n$ if $\ell<k$ , and some $t<n$ for larger $\ell$ , we seek a $k\text{-}\mathsf{EFTS}$ solution $H$ such that for $F\subseteq E$ with $|F|\geq k$ , $G-F$ and $H-F$ have the same components of weak-diameter at most $t$ .

1.1 Our contributions

We introduce cut-relative network-design problems and develop strong approximation guarantees for these problems. We obtain an approximation guarantee of $2$ for cut-relative $\mathsf{SNDP}$ , which, notably, matches the best-known approximation factor for $\mathsf{SNDP}$ . Our guarantee applies more generally to $\mathsf{CR}\text{-}{f}\text{-}\mathsf{NDP}$ , whenever the base cut-requirement function $f$ satisfies certain properties and the natural LP-relaxation of the problem $(\text{{CRLP}}_{f,G})$ can be solved efficiently. Our guarantee is relative to the optimal value of this LP, and is tight in that it matches the integrality gap of this LP.

We also show that even in the simplest $\mathsf{SNDP}$ setting with only one $s$ - $t$ pair (wherein $\mathsf{SNDP}$ is polytime solvable), cut-relative $\mathsf{SNDP}$ and path-relative $\mathsf{SNDP}$ capture $k\text{-}\mathsf{ECSS}$ as a special case, and are thus APX-hard (Section 6). Previously, even NP-hardness of path-relative $\mathsf{SNDP}$ in the $s$ - $t$ case (which is studied by [8, 9]) was not known.

Technical contributions and overview.

Technically, our main contribution is to show that we can obtain such a strong guarantee despite the fact that the cut-requirement function defining cut-relative network-design (i.e., $g^{\mathsf{CR}\text{-}{f}\text{-}\mathsf{NDP}}$ ) is not weakly supermodular, which is the key property that drives the $2$ -approximation algorithm for $\mathsf{SNDP}$ . To elaborate, there is a celebrated $2$ -approximation algorithm for $\mathsf{SNDP}$ due to Jain [15] based on iterative rounding. This crucially exploits the fact that the underlying cut-requirement function $f^{\mathsf{SNDP}}$ is weakly supermodular: for any two node-sets $A,B\subseteq V$ , we have:

f^{\mathsf{SNDP}}(A)+f^{\mathsf{SNDP}}(B)\leq\max\bigl\{f^{\mathsf{SNDP}}(A% \cap B)+f^{\mathsf{SNDP}}(A\cup B),\ f^{\mathsf{SNDP}}(A-B)+f^{\mathsf{SNDP}}(% B-A)\}.

This property allows one to argue that given an LP-solution $x$ , any two tight sets that cross – i.e., sets $A, B$ for which $x(S)=f^{\mathsf{SNDP}}(S)$ holds for $S\in\{A,B\}$ and $A\cap B,A-B,B-A$ are all non-empty – can be “uncrossed”, and thereby an extreme-point solution $\widehat{x}$ to the LP can be defined via a laminar family of tight cut constraints. By a laminar family, we mean that any two sets $A, B$ in the family satisfy $A\cap B=\emptyset$ or $A\subseteq B$ , and uncrossing two crossing tight sets means that they can be replaced by an equivalent laminar family of tight sets. Jain’s seminal contribution was to show that given such a laminar family defining an extreme point, there always exists an edge $e$ for which $\widehat{x}_{e}\geq\frac{1}{2}$ ; picking such an edge and iterating then yields the $2$ -approximation. This technique of uncrossing tight cut-constraints to obtain a laminar family of tight cut-constraints has proved to be quite versatile, becoming a staple technique that has been leveraged to obtain strong guarantees in various network-design settings such as, most notably, network-design problems with degree constraints [13, 17, 19, 5, 4, 16]. More generally, this technique of uncrossing to obtain a structured family of tight constraints has been utilized for various combinatorial-optimization problems; see, e.g., [18].

As mentioned earlier, the main complication with $\mathsf{CR}\text{-}{f}\text{-}\mathsf{NDP}$ is that the underlying cut-requirement function $g^{\mathsf{CR}\text{-}{f}\text{-}\mathsf{NDP}}$ is usually not weakly-supermodular, even if the base cut-requirement function $f$ is. In particular, the cut-requirement function $g^{\mathsf{CR}\text{-}\mathsf{SNDP}}$ defining cut-relative $\mathsf{SNDP}$ is not weakly-supermodular. This difficulty was also noted by Dinitz et al. [8] when they considered $k$ -edge fault-tolerant subgraph ( $k\text{-}\mathsf{EFTS}$ , or path- or cut- relative $k\text{-}\mathsf{ECSS}$ in our terminology). For this special case, they identify a notion called local weak-supermodularity that is satisfied by the cut-requirement function $\min\{k,|\delta_{G}(S)\}$ for $k\text{-}\mathsf{EFTS}$ , and observed that Jain’s machinery can be used as is if this property holds; that is, one can uncross tight sets to obtain a laminar family, and hence obtain a $2$ -approximation for $k\text{-}\mathsf{EFTS}$ proceeding as in Jain’s algorithm for $\mathsf{SNDP}$ .

However, for general $\mathsf{CR}\text{-}\mathsf{SNDP}$ , such an approach breaks down, because, as we show in Section 2.1, one can construct quite simple $\mathsf{CR}\text{-}\mathsf{SNDP}$ instances where an (optimal) extreme point cannot be defined by any laminar family of tight cut constraints. In particular, this implies that the cut-requirement function $g^{\mathsf{CR}\text{-}{f}\text{-}\mathsf{NDP}}$ is (in general) not locally weakly-supermodular (even when $f$ is weakly-supermodular); moreover, it does not satisfy any property that allows for the uncrossing of tight sets. The upshot here is that the standard technique of uncrossing tight sets to obtain a laminar family does not work, and one needs new ideas to deal with cut-relative network design.

The chief technical novelty of our work is to show how to overcome the impediment posed by the lack of any such nice structural property for $g^{\mathsf{CR}\text{-}{f}\text{-}\mathsf{NDP}}$ , via a novel decomposition technique that allows one to reduce cut-relative ${f}\text{-}\mathsf{NDP}$ with a weakly supermodular base cut-requirement function to (standard) ${f}\text{-}\mathsf{NDP}$ with (different) weakly supermodular cut-requirement functions (see Theorem 4.1).

We introduce a little notation to describe this. Let $\mathsf{CR}\text{-}{(h,D)}\text{-}\mathsf{NDP}$ denote $\mathsf{CR}\text{-}{f}\text{-}\mathsf{NDP}$ on graph $D$ with base cut-requirement function $h$ . For $S\subseteq V$ , define its deficiency to be $f(S)-|\delta_{G}(S)|$ ; we say that $S$ is a small cut if its deficiency is positive (i.e., $|\delta_{G}(S)|<f(S)$ ). We use $G[{S}]$ to denote the subgraph induced by $S$ . Let $\overline{S}$ denote $V-S$ .

Assume that the underlying base cut-requirement function $f$ is weakly supermodular (as is the case with $\mathsf{SNDP}$ ). Observe first that if there is no small cut then $\mathsf{CR}\text{-}{f}\text{-}\mathsf{NDP}$ is the same as ${f}\text{-}\mathsf{NDP}$ . Our key technical insight is that, otherwise, we can utilize a novel splitting operation to simplify our problem. We show (see Theorem 4.5) that if we pick a small cut $A\subseteq V$ with maximum deficiency, then one can define suitable weakly-supermodular functions $f_{A}:2^{A}\mapsto\mathbb{Z}$ and $f_{\overline{A}}:2^{\overline{A}}\mapsto\mathbb{Z}$ such that any solution to the original $\mathsf{CR}\text{-}{f}\text{-}\mathsf{NDP}$ -instance yields solutions to $\mathsf{CR}\text{-}{(f_{A},G[{A}])}\text{-}\mathsf{NDP}$ and $\mathsf{CR}\text{-}{(f_{\overline{A}},G[{\overline{A}}])}\text{-}\mathsf{NDP}$ , and vice-versa. The intuition here is as follows. Since $A$ is a small cut, any feasible $\mathsf{CR}\text{-}{f}\text{-}\mathsf{NDP}$ solution must include all edges in $\delta_{G}(A)$ . The functions $f_{A}$ and $f_{\overline{A}}$ are essentially the restrictions of $f$ to $A$ and $\overline{A}$ respectively, taking this into account. Consequently, moving to $\mathsf{CR}\text{-}{(f_{A},G[{A}])}\text{-}\mathsf{NDP}$ and $\mathsf{CR}\text{-}{(f_{\overline{A}},G[{\overline{A}}])}\text{-}\mathsf{NDP}$ does not really impact the constraints for cuts that do not cross $A$ ; but we do eliminate the constraints for crossing cuts. This is the simplification that we obtain via the splitting operation, and one needs to argue that this does not hurt feasibility; that is, the constraints for such cuts are still satisfied when we take $\delta_{G}(A)$ along with the $\mathsf{CR}\text{-}{(f_{A},G[{A}])}\text{-}\mathsf{NDP}$ and $\mathsf{CR}\text{-}{(f_{\overline{A}},G[{\overline{A}}])}\text{-}\mathsf{NDP}$ solutions. Here we exploit the weak-supermodularity of $f$ , which implies that the deficiency function $\operatorname{def}(S):=f(S)-|\delta_{G}(S)|$ is also weakly supermodular. One can use this, and the fact that $A$ has maximum deficiency, to bound the deficiency of any crossing set $T$ in terms of the deficiency of non-crossing sets, and hence show that the cut-constraint for $T$ is satisfied.

By recursively applying the above splitting operation to $A$ and $\overline{A}$ , we end up with a partition $V_{1},\ldots,V_{k}$ of $V$ and weakly-supermodular functions $f_{i}:2^{V_{i}}\mapsto\mathbb{Z}$ for all $i\in[k]$ such that, for each $i\in[k]$ , the graph $G[{V_{i}}]$ contains no small cut with respect to $f_{i}$ . It follows that solving ${f_{i}}\text{-}\mathsf{NDP}$ on the graph $G[{V_{i}}]$ for all $i\in[k]$ yields a solution to the original $\mathsf{CR}\text{-}{f}\text{-}\mathsf{NDP}$ instance (Theorem 4.1).

While we can obtain this decomposition efficiently, assuming that one has suitable algorithmic primitives involving the base cut-requirement function $f$ (shown in the full version), in fact we only need this decomposition in the analysis: in order to obtain the stated LP-relative $2$ -approximation algorithm, we only need to be able to find an extreme-point optimal solution to the natural LP-relaxation $(\text{{CRLP}}_{f,G})$ for $\mathsf{CR}\text{-}{f}\text{-}\mathsf{NDP}$ (also after fixing some variables to $1$ ). This is because the translation between $\mathsf{CR}\text{-}{f}\text{-}\mathsf{NDP}$ -solutions for $G$ , and ${f_{i}}\text{-}\mathsf{NDP}$ -solutions on $G[{V_{i}}]$ for all $i\in[k]$ , also applies to fractional solutions, and implies that any extreme-point solution to $(\text{{CRLP}}_{f,G})$ yields extreme-point solutions to the LP-relaxations of ${f_{i}}\text{-}\mathsf{NDP}$ on $G[{V_{i}}]$ for all $i\in[k]$ (parts (b) and (c) of Theorem 4.1); hence, by Jain’s result, we can always find some fractional edge of value at least $\frac{1}{2}$ , round its value to $1$ , and iterate. For $\mathsf{SNDP}$ , we can find an extreme-point optimal solution efficiently because we argue that one can devise an efficient separation oracle for $(\text{{CRLP}}_{f,G})$ (Lemma 2.3). This yields a $2$ -approximation algorithm for $\mathsf{CR}\text{-}\mathsf{SNDP}$ , and more generally $\mathsf{CR}\text{-}{f}\text{-}\mathsf{NDP}$ , whenever $f$ is weakly supermodular and $(\text{{CRLP}}_{f,G})$ can be solved efficiently (see Algorithm CRNDP-Alg in Section 5).

Other related work.

Network design is a fairly broad research topic, with a vast amount of literature. We limit ourselves to the work that is most closely connected to our work.

As mentioned earlier, path-relative $\mathsf{SNDP}$ was introduced by Dinitz et al. [8]. In addition to $k\text{-}\mathsf{EFTS}$ , which is the path-relative version of $k\text{-}\mathsf{ECSS}$ , they study the path-relative versions of two other special cases of $\mathsf{SNDP}$ , for which they developed constant-factor approximation algorithms: (1) $\mathsf{SNDP}$ with $r_{i}\leq 2$ for all $i$ ; (2) one $s_{i}$ - $t_{i}$ pair with $r_{i}\leq 3$ . Both results were subsequently extended by [9] who gave a $2$ -approximation for $\mathsf{SNDP}$ with $r_{i}\leq 3$ for all $i$ , and a $2^{O(k^{2})}$ -approximation when there is one $s_{i}$ - $t_{i}$ pair with $r_{i}=k$ . The only result known for general path-relative $\mathsf{SNDP}$ is due to [7], who (among other results) devise an $O(k^{2}\log^{2}n\log\log n)$ -approximation algorithm with $n^{O(k)}$ running time. As noted earlier, on the hardness side, prior to our work, it was not known if the setting with one $s_{i}$ - $t_{i}$ pair is even NP-hard.

An influential paper by Goemans and Williamson [10] (see also the survey [11]), which built upon the work of [1] for the Steiner forest problem, developed the primal-dual method for network-design problems. Their work also popularized the use of cut-requirement functions to specify network-design problems, by showing how this framework can be used to capture a slew of problems, and how their primal-dual framework leads to a $2$ -approximation algorithm for $\{0,1\}$ -cut-requirement functions satisfying some properties. This work was extended to handle general integer-valued cut-requirement functions, which captures $\mathsf{SNDP}$ , in [20, 12], which led to an $O(\log\max_{i}r_{i})$ -approximation for $\mathsf{SNDP}$ . The seminal work of Jain [15] later improved this to a $2$ -approximation, and in doing so, introduced the powerful technique of iterative rounding. Later work of [17, 19] on degree-bounded network design added another ingredient to iterative rounding, namely iteratively dropping some constraints. This paradigm of iterative rounding and relaxation has proved to be an extremely versatile and powerful tool in developing algorithms (and structural results) for network-design problems, and more generally in combinatorial optimization; see [18] for an extensive study.

Iterative rounding and relaxation derives its power from the fact that an extreme-point solution to an LP-relaxation of the problem can be defined using a structured family of tight constraints, such as, often a laminar family of cut constraints in the case of network-design problems. As noted earlier, this key property does not hold for cut-relative $\mathsf{SNDP}$ (and path-relative $\mathsf{SNDP}$ ). Recently, various works have considered network-design problems that give rise to cut constraints that are less structured and not quite uncrossable; see [2, 3, 6] and the references therein. Our work can be seen as furthering this research direction.

2 Preliminaries and notation

Recall that we are given an undirected graph $G=(V,E)$ with nonnegative edge costs $\{c_{e}\}_{e\in E}$ . For a subset $S\subseteq V$ and subset $Z\subseteq E$ , which we will interchangeably view as the subgraph $(V,Z)$ of $G$ , we use $\delta_{Z}(S)$ to denote $\delta_{G}(S)\cap Z$ , i.e., the edges of $Z$ on the boundary of $S$ . Recall that $\overline{S}$ denotes $V-S$ , and $G[{S}]$ denotes the subgraph induced by $S$ . A cut-requirement function on $G$ is a function $f:2^{V}\mapsto\mathbb{Z}$ . (We allow $f(S)$ to be negative chiefly for notational simplicity; this does not affect anything, as we will only examine sets for which $f(S)\geq 0$ .) Recall the following network-design problems.

$\blacksquare$

$f$ -network-design problem ( ${f}\text{-}\mathsf{NDP}$ ): find a min-cost edge-set $H$ such that $|\delta_{H}(S)|\geq f(S)$ for all $S\subseteq V$ .
$\blacksquare$

Cut-relative network-design problem ( $\mathsf{CR}\text{-}{f}\text{-}\mathsf{NDP}$ ): find a min-cost edge-set $H$ such that $|\delta_{H}(S)|\geq g^{\mathsf{CR}\text{-}{f}\text{-}\mathsf{NDP}}(S):=\min% \bigl\{f(S),|\delta_{G}(S)|\bigr\}$ for all $S\subseteq V$ . This corresponds to ${g^{\mathsf{CR}\text{-}{f}\text{-}\mathsf{NDP}}}\text{-}\mathsf{NDP}$ . We call $f$ the base cut-requirement function.
$\blacksquare$

Survivable network design problem ( $\mathsf{SNDP}$ ) is a special case of ${f}\text{-}\mathsf{NDP}$ . The input also specifies $k$ tuples $\{(s_{i},t_{i},r_{i})\}_{i\in[k]}$ , where $s_{i},t_{i}\in V$ and $r_{i}\in\mathbb{Z}_{+}$ for all $i\in[k]$ . Defining $f^{\mathsf{SNDP}}(S):=\max\,\{r_{i}:|S\cap\{s_{i},t_{i}\}|=1\}$ for all $S\subseteq V$ , we obtain that $\mathsf{SNDP}$ is the $f^{\mathsf{SNDP}}$ -network-design problem.
$\blacksquare$

Cut-relative $\mathsf{SNDP}$ ( $\mathsf{CR}\text{-}\mathsf{SNDP}$ ): The input here is the same as in $\mathsf{SNDP}$ . In Definition 1.1 (R2), $\mathsf{CR}\text{-}\mathsf{SNDP}$ was defined as: find a min-cost $H\subseteq E$ such that for every $i\in[k]$ , every $F\subseteq E$ with $|F|<r_{i}$ , and every $s_{i}$ - $t_{i}$ cut $S$ , we have $\delta_{H-F}(S)\neq\emptyset$ whenever $\delta_{G-F}(S)\neq\emptyset$ . Later in Section 1, we stated that this can be equivalently formulated as $\mathsf{CR}\text{-}{f}\text{-}\mathsf{NDP}$ with base cut-requirement function $f^{\mathsf{SNDP}}$ . We now justify this statement.

Suppose that $H$ is feasible under (R2) but $|\delta_{H}(S)|<\min\bigl\{f^{\mathsf{SNDP}}(S),|\delta_{G}(S)|\bigr\}$ for some $S\subseteq V$ . Suppose $f^{\mathsf{SNDP}}(S)=r_{i}$ . Then taking $F=\delta_{H}(S)$ , we have $|F|<r_{i}$ , $\delta_{G-F}(S)\neq\emptyset$ , but $\delta_{H-F}(S)=\emptyset$ , yielding a contradiction. So $H$ is feasible for $\mathsf{CR}\text{-}{f^{\mathsf{SNDP}}}\text{-}\mathsf{NDP}$ . Conversely, suppose $H$ is feasible for $\mathsf{CR}\text{-}{f^{\mathsf{SNDP}}}\text{-}\mathsf{NDP}$ . Consider any $i\in[k]$ , any $F\subseteq E$ with $|F|<r_{i}$ , and any $s_{i}$ - $t_{i}$ cut $S$ with $\delta_{G-F}(S)\neq\emptyset$ . Then, $|\delta_{F}(S)|<\min\bigl\{r_{i},|\delta_{G}(S)|\bigr\}\leq\min\bigl\{f(S),|% \delta_{G}(S)|\bigr\}\leq|\delta_{H}(S)|$ ; so $\delta_{H-F}(S)\neq\emptyset$ , showing that $H$ satisfies (R2).

We will consider network-design problems defined on various graphs and with various cut-requirement functions. Given a graph $D=(V_{D},E_{D})$ and cut-requirement function $h:2^{V_{D}}\mapsto\mathbb{Z}$ , we use ${(h,D)}\text{-}\mathsf{NDP}$ to denote ${f}\text{-}\mathsf{NDP}$ on the graph $D$ with cut-requirement function $h$ , and $\mathsf{CR}\text{-}{(h,D)}\text{-}\mathsf{NDP}$ to denote $\mathsf{CR}\text{-}{f}\text{-}\mathsf{NDP}$ on the graph $D$ with base cut-requirement function $h$ .

Properties of cut-requirement functions.

Let $f:2^{V}\mapsto\mathbb{R}$ . We say that $f$ is weakly supermodular if for any two node-sets $A,B\subseteq V$ , we have $f(A)+f(B)\leq\max\bigl\{f(A\cap B)+f(A\cup B),\,f(A-B)+f(B-A)\bigr\}$ . We say that $f$ is symmetric if $f(S)=f(V-S)$ for all $S\subseteq V$ , and is normalized if $f(\emptyset)=f(V)=0$ .

Since we are working on undirected graphs, we can always replace any cut-requirement function $f$ by its symmetric, normalized version $f^{\mathsf{sym}}$ , where $f^{\mathsf{sym}}(S):=\max\{f(S),f(V-S)\}$ for all $\emptyset\neq S\subsetneq V$ and $f^{\mathsf{sym}}(\emptyset)=f^{\mathsf{sym}}(V):=0$ , without changing the resulting network-design problem(s), i.e., we have ${f}\text{-}\mathsf{NDP}\equiv{f^{\mathsf{sym}}}\text{-}\mathsf{NDP}$ and $\mathsf{CR}\text{-}{f}\text{-}\mathsf{NDP}\equiv\mathsf{CR}\text{-}{f^{\mathsf% {sym}}}\text{-}\mathsf{NDP}$ .

Lemma 2.1 shows that weak-supermodularity is preserved under various operations. This will be quite useful in the analysis of our decomposition technique. Part a of the lemma shows that weak supermodularity is preserved under symmetrization and normalization, so for any ${f}\text{-}\mathsf{NDP}$ or $\mathsf{CR}\text{-}{f}\text{-}\mathsf{NDP}$ instance involving a weakly-supermodular base cut-requirement function $f$ , we may assume that $f$ is symmetric and normalized.

All omitted proofs and details can be found in the full version of the paper.

Lemma 2.1.

Let $f:2^{V}\mapsto\mathbb{R}$ be weakly supermodular. Then

(a)

$f^{\mathsf{sym}}$ is weakly supermodular.
(b)

Let $w\in\mathbb{R}_{+}^{E}$ . Define $g_{1}(S):=f(S)-w\bigl(\delta_{G}(S)\bigr)$ for all $S\subseteq V$ . Then $g_{1}$ is weakly supermodular, and $g_{1}$ is symmetric if $f$ is symmetric. In particular, for any $Z\subseteq E$ , the function $f(S)-|\delta_{Z}(S)|$ is weakly supermodular, and is symmetric if $f$ is symmetric.
(c)

Let $X\subseteq V$ , and $\mathcal{C}$ be a collection of subsets of $V-X$ closed under taking set intersections, unions, differences, and complements with respect to $V-X$ , i.e., if $S\in\mathcal{C}$ then $V-X-S\in\mathcal{C}$ , and $S,T\in\mathcal{C}$ implies that $\{S\cap T,S\cup T,S-T,T-S\}\subseteq\mathcal{C}$ .

Define the projection of $f$ onto $X$ with respect to $\mathcal{C}$ as the function $g_{2}:2^{X}\mapsto\mathbb{R}$ given by $g_{2}(\emptyset)=g_{2}(X):=0$ , and $g_{2}(S):=\max_{T\in\mathcal{C}}f(S\cup T)$ for all $\emptyset\neq S\subsetneq X$ . If $f$ is symmetric, then $g_{2}$ is weakly supermodular and symmetric.

Proof.

Part (a) follows from a simple case analysis; part (b) follows because $w\bigl(\delta_{G}(S)\bigr)$ is symmetric, submodular. We focus on proving part (c). Essentially, the closure properties of $\mathcal{C}$ enable us to transfer the weak-supermodularity of $f$ to the function $g_{2}$ .

We first argue that $g_{2}$ is symmetric. If $A\in\{\emptyset,X\}$ , we have $g_{2}(A)=g_{2}(X-A)$ by definition. Otherwise, if $g_{2}(A)=f(A\cup T_{A})$ , we have $f(A\cup T_{A})=f\bigl(V-(A\cup T_{A})\bigr)=f\bigl((X-A)\cup(V-X-T_{A})\bigr)% \leq g_{2}(X-A)$ where the last inequality follows since $V-X-T_{A}\in\mathcal{C}$ . We also have $g_{2}(X-A)\leq g_{2}(A)$ by the same type of reasoning, and so $g_{2}(A)=g_{2}(X-A)$ for all $A\subseteq X$ .

Now we show that $g_{2}$ is weakly supermodular. Consider $A,B\subseteq X$ . If any of the sets $A-B,B-A,A\cap B,X-(A\cup B)$ are empty, then $g_{2}(A)+g_{2}(B)=g_{2}(A\cap B)+g_{2}(A\cup B)$ or $g_{2}(A)+g_{2}(B)=g_{2}(A-B)+g_{2}(B-A)$ . The former holds when $A-B$ or $B-A$ is empty; the latter holds when $A\cap B$ or $X-(A\cup B)$ is empty, where we also utilize the fact that $g_{2}$ is symmetric. So assume otherwise. Then, for every $S\in\{A,B,A\cap B,A\cup B,A-B,B-A\}$ , we have $g_{2}(S)=\max_{T\in\mathcal{C}}f(S\cup T)$ .

Let $g_{2}(A)=f(A\cup T_{A})$ and $g_{2}(B)=f(B\cup T_{B})$ , where $T_{A},T_{B}\in\mathcal{C}$ . Let $A^{\prime}=A\cup T_{A}$ and $B^{\prime}=B\cup T_{B}$ . For any $S\in\{A^{\prime}\cap B^{\prime},A^{\prime}\cup B^{\prime},A^{\prime}-B^{\prime% },B^{\prime}-A^{\prime}\}$ , we can write $S=(S\cap X)\cup T$ , where $T\in\mathcal{C}$ due to the closure properties of $\mathcal{C}$ . It follows that $g_{2}(S\cap X)\geq f(S)$ for all $S\in\{A^{\prime}\cap B^{\prime},A^{\prime}\cup B^{\prime},A^{\prime}-B^{\prime% },B^{\prime}-A^{\prime}\}$ . So if $f(A^{\prime})+f(B^{\prime})\leq f(A^{\prime}\cap B^{\prime})+f(A^{\prime}\cup B% ^{\prime})$ , we obtain that $g_{2}(A)+g_{2}(B)\leq g_{2}(A\cap B)+g_{2}(A\cup B)$ , and if $f(A^{\prime})+f(B^{\prime})\leq f(A^{\prime}-B^{\prime})+f(B^{\prime}-A^{% \prime})$ , we obtain that $g_{2}(A)+g_{@}(B)\leq g_{2}(A-B)+g_{2}(B-A)$ . $\hfill\blacktriangleleft$

The intuition behind the projection operation is as follows. Suppose $f$ is a cut-requirement function and we know that no edges are picked from $E_{G}(V-X)\cup\delta_{G}(X)$ . Then, roughly speaking, $g_{2}(S)$ captures the constraints that arise on $S\subseteq X$ due to $f$ and $\mathcal{C}$ .

2.1 LP-relaxation for CR- $𝒇$ -NDP

We consider the following natural LP-relaxation for $\mathsf{CR}\text{-}{f}\text{-}\mathsf{NDP}$ . From now on, we assume that the cut-requirement function $f:2^{V}\mapsto\mathbb{Z}$ is weakly supermodular, symmetric, and normalized. Given $\alpha\in\mathbb{R}^{E}$ and $F\subseteq E$ , let $\alpha(F)$ denote $\sum_{e\in F}\alpha_{e}$ .

$\displaystyle\min$		$\displaystyle\sum_{e\in E}c_{e}x_{e}$			$(\text{{CRLP}}_{f,G})$
s.t.		$\displaystyle x\bigl(\delta_{G}(S)\bigr)$	$\displaystyle\geq\min\bigl\{f(S),\|\delta_{G}(S)\|\bigr\}\qquad$	$\displaystyle\forall S\subseteq V$	(1)
$\displaystyle 0\leq x_{e}$	$\displaystyle\leq 1$	$\displaystyle\forall e\in E.$			(2)

The LP-relaxation for ${f}\text{-}\mathsf{NDP}$ is similar, with the cut-constraints taking the simpler form $x\bigl(\delta_{G}(S)\bigr)\geq f(S)$ for all $S\subseteq V$ . We denote this LP by $(\text{{NDP}}_{f,G})$ . Our algorithm is based on iterative rounding, where we iteratively fix some $x_{e}$ variables to $1$ . Suppose that we have fixed $x_{e}=1$ for all $e\in Z_{1}$ . Then, in that iteration, we are considering the residual problem on the subgraph $G^{\prime}=(V,E^{\prime}=E-Z_{1})$ , which leads to the following variant of $(\text{{CRLP}}_{f,G})$ :

$\displaystyle\min$		$\displaystyle\sum_{e\in E^{\prime}}c_{e}x_{e}$			(P’)
s.t.		$\displaystyle x\bigl(\delta_{G^{\prime}}(S)\bigr)$	$\displaystyle\geq\min\bigl\{f(S),\|\delta_{G}(S)\|\bigr\}-\|\delta_{Z_{1}}(S)\|\qquad$	$\displaystyle\forall S\subseteq V$	(3)
$\displaystyle 0\leq x_{e}$	$\displaystyle\leq 1$	$\displaystyle\forall e\in E^{\prime}.$

Defining $f^{\prime}(S)=f(S)-|\delta_{Z_{1}}(S)|$ for all $S\subseteq V$ , we can rephrase constraints (3) as $x\bigl(\delta_{G^{\prime}}(S)\bigr)\geq\min\bigl\{f^{\prime}(S),|\delta_{G^{% \prime}}(S)|\}$ for all $S\subseteq V$ . Since $f^{\prime}$ is weakly supermodular, symmetric (Lemma 2.1 (b)), and normalized, (P’) is of the same form as $(\text{{CRLP}}_{f,G})$ : we have (P’) $\equiv(\text{{CRLP}}_{f^{\prime},G^{\prime}})$ . This will be convenient for iterative rounding, as the residual problem is of the same form as the original problem. $(\text{{CRLP}}_{f,G})$ and (P’) involve an exponential number of constraints, but using the ellipsoid method, we can find an extreme-point optimal solution provided we have a separation oracle for them. Recall that a separation oracle is a procedure that given a candidate point determines if it is feasible, or returns a violated inequality. Observe that a separation oracle for $(\text{{CRLP}}_{f,G})$ also yields a separation oracle for (P’), since (P’) is simply $(\text{{CRLP}}_{f,G})$ after fixing some variables to $1$ .

Fact 2.2 (Ellipsoid method [14]).

Given a polytime separation oracle for $(\text{{CRLP}}_{f,G})$ , one can find an extreme-point optimal solution to LPs $(\text{{CRLP}}_{f,G})$ and (P’) in polytime.

For $\mathsf{CR}\text{-}\mathsf{SNDP}$ , i.e., when $f=f^{\mathsf{SNDP}}$ , a polytime separation oracle for $(\text{{CRLP}}_{f,G})$ can be obtained using min-cut computations. This was shown by [8] for path-relative $k\text{-}\mathsf{ECSS}$ , which is equivalent to cut-relative $k\text{-}\mathsf{ECSS}$ ; refining their ideas yields a separation oracle for $(\text{{CRLP}}_{f,G})$ for general $\mathsf{SNDP}$ .

Lemma 2.3.

When $f=f^{\mathsf{SNDP}}$ , there is a polytime separation oracle for $(\text{{CRLP}}_{f,G})$ . Hence, one can obtain extreme-point optimal solutions to $(\text{{CRLP}}_{f,G})$ and (P’) in polytime.

Proof.

The second statement follows from Fact 2.2. Let $(s_{i},t_{i},r_{i})_{i\in[k]}$ be the $k$ tuples defining the $\mathsf{SNDP}$ instance, which recall leads to the cut-requirement function $f^{\mathsf{SNDP}}(S):=\max\,\{r_{i}:|S\cap\{s_{i},t_{i}\}|=1\}$ for all $S\subseteq V$ . Say that $S\subseteq V$ is a small cut if $f^{\mathsf{SNDP}}(S)>|\delta_{G}(S)|$ , and it is a small cut for $i$ if $|S\cap\{s_{i},t_{i}\}|=1$ and $r_{i}>|\delta_{G}(S)|$ . Note that if $e\in\delta_{G}(S)$ for any small cut $S$ , then we must have $x_{e}=1$ in any feasible solution.

Now we can equivalently phrase the constraints of $(\text{{CRLP}}_{f,G})$ as follows: for any edge $a=uv\in E$ , we must have $x_{a}=1$ or, for every $i\in[k]$ , the minimum $s_{i}$ - $t_{i}$ cut also separating $u$ and $v$ under the $\{x_{e}\}_{e\in E}$ -capacities should have capacity at least $r_{i}$ . So to detect if $x$ is a feasible solution, we simply need to consider every edge $a=uv$ with $x_{a}<1$ and every $i\in[k]$ , and find the minimum $s_{i}$ - $t_{i}$ cut also separating $u$ and $v$ under the $\{x_{e}\}_{e\in E}$ capacities. If an $s_{i}$ - $t_{i}$ cut separates $u, v$ , then $u$ lies on the $s_{i}$ -side and $v$ lies on the $t_{i}$ -side, or the other way around. So to find the minimum $s_{i}$ - $t_{i}$ cut also separating $u$ and $v$ , we find the minimum $\{s_{i},u\}$ - $\{t_{i},v\}$ cut – by which we mean the minimum $s_{i}$ - $t_{i}$ cut where $s_{i},u$ are on the same side, and $t_{i},v$ are on the other side–and the minimum $\{s_{i},v\}$ - $\{t_{i},u\}$ -cut and take the one with smaller capacity. $\hfill\blacktriangleleft$

Extreme-point solution to $(\text{{CRLP}}_{f,G})$ not defined by a laminar family

We show that for the $\mathsf{CR}\text{-}\mathsf{SNDP}$ instance shown in Fig. 1, the extreme-point solution $\widehat{x}$ shown in the figure, cannot be expressed as the solution to any laminar family of tight cut constraints (1) (along with tight edge constraints (2)). The $\mathsf{SNDP}$ instance is $s$ - $t$ $2$ -edge connectivity: that is, the base cut-requirement function is given by $f(S)=2$ if $S$ is an $s$ - $t$ cut, and $f(S)=0$ otherwise.

Refer to caption — Figure 1: $\mathsf{CR}\text{-}\mathsf{SNDP}$ instance, and an extreme-point solution $\widehat{x}$ to $(\text{{CRLP}}_{f,G})$ . The solid edges have $\widehat{x}_{e}=1$ and the dashed edges have $\widehat{x}_{e}=0.5$ , so $\widehat{x}_{e}=0.5$ for $e\in\{su,uw,sv,vw\}$ and $\widehat{x}_{e}=1$ for $e\in\{sw,wt\}$ .

Note that the only small cut above containing $s$ is $S=\{s,u,v,w\}$ . One can verify by inspection that $\widehat{x}$ is feasible. It is not hard to see that $\widehat{x}$ is the unique solution to the following set of equations, which come from constraints that are tight at $\widehat{x}$ .

	$\displaystyle x\bigl(\delta(S)\bigr)$	$\displaystyle=2\qquad\forall S\in\bigl\{\{s\},\{s,u,v\},\{s,u,w\},\{s,v,w\}% \bigr\},$		(4)
	$\displaystyle x_{e}$	$\displaystyle=1\qquad\forall e\in\{sw,wt\}.$		(5)

This shows that $\widehat{x}$ is an extreme-point solution to $(\text{{CRLP}}_{f,G})$ . With edge costs $c_{sw}=0$ and $c_{e}=1$ for all other edges, $\widehat{x}$ is also an optimal solution. The constraints $x\bigl(\delta(S)\bigr)\geq 2$ for all $S\in\bigl\{\{s\},\{s,u,v\},\{s,u,w\},\{s,v,w\}\bigr\}$ imply that (since $x_{e}\leq 1$ for all $e$ )

x_{su}+x_{sv}\geq 1,\quad x\bigl(\delta(u)\bigr)\geq 1,\quad x\bigl(\delta(v)% \bigr)\geq 1,\quad x_{uw}+x_{vw}\geq 1.

Adding these constraints, we obtain that $x_{su}+x_{sv}+x_{uv}+x_{vw}\geq 2$ . Therefore, the cost of any feasible solution is at least $3$ , and we have $c^{T}\widehat{x}=3$ .

$\widehat{x}$ cannot be defined via a laminar family.

We now argue that $\widehat{x}$ cannot be defined by any laminar family of tight cut constraints and tight edge constraints. Note that any tight cut constraint corresponds to an $s$ - $t$ cut. So a laminar family $\mathcal{L}$ of tight cut constraints consists of a union of two chains $\mathcal{L}_{1}\cup\mathcal{L}_{2}$ , where a chain is a nested collection of sets: $\mathcal{L}_{1}$ comprising sets containing $s$ but not $t$ , and $\mathcal{L}_{2}$ comprising sets containing $t$ but not $s$ . Then $\mathcal{L}^{\prime}=\mathcal{L}_{1}\cup\{V-S:S\in\mathcal{L}_{2}\}$ is also a laminar family, yielding the same cut-constraints as $\mathcal{L}$ , and and all sets in $\mathcal{L}^{\prime}$ contain $s$ but not $t$ . So we only need to consider laminar families of tight cut constraints corresponding to a chain of sets containing $s$ and not $t$ .

A simple argument now rules out the existence of any such chain that can uniquely define $\widehat{x}$ along with the tight edge constraints (5). Any such chain of sets $\mathcal{C}$ is obtained by ordering the elements $u, v, w$ , and taking sets of the form $\{s\}\cup T$ , where $T$ is some prefix (including the empty prefix) of this ordered sequence; so $\mathcal{C}$ contains at most $4$ sets. Since $\widehat{x}$ has $4$ fractional edges, $E^{\prime}=\{su,sv,uw,vw\}$ , it must be that $\bigl\{\chi^{\delta_{E^{\prime}}(S)}\}_{S\in\mathcal{C}}$ contains $4$ linearly independent vectors. So $\mathcal{C}$ contains exactly $4$ sets, and in particular the set $\{s,u,v,w\}$ , and all vectors in $\bigl\{\chi^{\delta_{E^{\prime}}(S)}\}_{S\in\mathcal{C}}$ are linearly independent. This yields a contradiction, since $\chi^{\delta_{E^{\prime}}(\{s,u,v,w\})}=\vec{0}$ .

3 Modeling power of CR- $𝒇$ -NDP

We prove that the $\mathsf{CR}\text{-}{f}\text{-}\mathsf{NDP}$ Examples 1.2 and 1.3 listed under “Modeling power” in Section 1 model the stated problems. Recall that in both examples, we have a non-increasing function $\tau:\mathbb{Z}_{+}\mapsto\mathbb{Z}_{+}$ .

Theorem 3.1.

Consider the base cut-requirement function $f^{\mathsf{grace}}$ in Example 1.2, where $f^{\mathsf{grace}}(S):=\min\,\{\ell:\tau(\ell)<|S|\}$ , for $S\neq\emptyset$ .

(a)

The function $f^{\mathsf{grace}}$ is weakly-supermodular.
(b)

$H$ is feasible for $\mathsf{CR}\text{-}{f^{\mathsf{grace}}}\text{-}\mathsf{NDP}$ iff for every fault-set $F\subseteq E$ , and every $S\subseteq V$ with $|S|\leq\tau(|F|)$ , $S$ is (the node-set of) a component of $G-F$ iff it is a component of $H-F$ .

Proof.

The function $f^{\mathsf{grace}}$ is downwards-monotone: if $\emptyset\neq T\subseteq S$ , then $f^{\mathsf{grace}}(T)\geq f^{\mathsf{grace}}(S)$ . This follows from the definition, since $\tau$ is a non-increasing function. Weak-supermodularity of $f^{\mathsf{grace}}$ is now immediate since we have $f^{\mathsf{grace}}(A)+f^{\mathsf{grace}}(B)\leq f^{\mathsf{grace}}(A-B)+f^{% \mathsf{grace}}(B-A)$ , if $A-B,B-A\neq\emptyset$ , and otherwise $f^{\mathsf{grace}}(A)+f^{\mathsf{grace}}(B)=f^{\mathsf{grace}}(A\cap B)+f^{% \mathsf{grace}}(A\cup B)$ .

Note that $f^{\mathsf{grace}}$ is not symmetric or normalized, but as indicated by Lemma 2.1, we can consider $\mathsf{CR}\text{-}{f}\text{-}\mathsf{NDP}$ with the symmetric, normalized version of $f^{\mathsf{grace}}$ as the base cut-requirement function, without changing the problem.

To prove the feasibility characterization in part (b), we note that the function $f^{\mathsf{grace}}$ is constructed so that for any $S\subseteq V$ and $F\subseteq E$ , we have $|S|\leq\tau(|F|)$ iff $f^{\mathsf{grace}}(S)>|F|$ , so that $|\delta_{H}(S)|\geq f^{\mathsf{grace}}(S)$ implies that $S$ is not a component of $H-F$ . Suppose $H$ is such that $|\delta_{H}(S)|\geq\min\bigl\{f^{\mathsf{grace}}(S),|\delta_{G}(S)|\bigr\}$ for all $S\subseteq V$ . Consider any fault-set $F\subseteq E$ and any $S\subseteq V$ such that $|S|\leq\tau(|F|)$ . By the above, if $S$ is a component of $H-F$ , then $|\delta_{H}(S)|<f^{\mathsf{grace}}(S)$ , and so $S$ must also be a component of $G-F$ . But this also implies that if $S$ is a component of $G-F$ , then it is a component of $H-F$ ; otherwise, there is some $A\subsetneq S$ that is a component of $H-F$ with $|A|<|S|\leq\tau(|F|)$ , and so $A$ must be a component of $G-F$ , which is not the case.

Conversely, suppose that for every $F\subseteq E$ , and $S\subseteq V$ with $|S|\leq\tau(|F|)$ , we have that $S$ is a component of $G-F$ iff it is a component of $H-F$ . If $|\delta_{H}(S)|<\min\bigl\{f^{\mathsf{grace}}(S),|\delta_{G}(S)|\bigr\}$ for some $S\subseteq V$ , then take $F=\delta_{H}(S)$ . Since $f^{\mathsf{grace}}(S)>|F|$ , we have $|S|\leq\tau(|F|)$ . But $S$ is a component of $H-F$ and not $G-F$ , which yields a contradiction. $\hfill\blacktriangleleft$

Theorem 3.2.

Let $\pi:2^{V}\mapsto\mathbb{R}_{+}$ be a monotone function, i.e., $\pi(T)\leq\pi(S)$ if $T\subseteq S$ , as in Example 1.3. Consider $\mathsf{CR}\text{-}{f}\text{-}\mathsf{NDP}$ , where the base cut-requirement function $f$ is given by $f(S):=\min\,\{\ell:\tau(\ell)<\pi(S)\}$ , for all $S\neq\emptyset$ . Then

(a)

$f$ is weakly-supermodular;
(b)

$H$ is feasible for $\mathsf{CR}\text{-}{f}\text{-}\mathsf{NDP}$ iff for every fault-set $F\subseteq E$ , and every $S\subseteq V$ with $\pi(S)\leq\tau(|F|)$ , $S$ is (the node-set of) a component of $G-F$ iff it is a component of $H-F$ .

Proof.

We mimic the proof of Theorem 3.1. Since $\pi$ is monotone, we obtain that $f$ is downwards-monotone, and hence weakly-supermodular.

For part (b), similar to before, we have that $\pi(S)\leq\tau(|F|)$ iff $f(S)>|F|$ . Suppose $H$ is feasible for $\mathsf{CR}\text{-}{f}\text{-}\mathsf{NDP}$ . Consider any fault-set $F\subseteq E$ and any $S\subseteq V$ be such that $\pi(S)\leq\tau(|F|)$ . By the above, $f(S)>|F|$ , so if $S$ is a component of $H-F$ , then it must also be a component of $G-F$ . Again, this also implies that if $S$ is a component of $G-F$ , then it is a component of $H-F$ : otherwise, there is some $A\subsetneq S$ that is a component of $H-F$ , and $\pi(A)\leq\pi(S)\leq\tau(|F|)$ , which means that $A$ is a component of $G-F$ .

Conversely, suppose that for every $F\subseteq E$ , and $S\subseteq V$ with $\pi(S)\leq\tau(|F|)$ , we have that $S$ is a component of $G-F$ iff it is a component of $H-F$ . If $|\delta_{H}(S)|<\min\bigl\{f(S),|\delta_{G}(S)|\bigr\}$ for some $S\subseteq V$ , then take $F=\delta_{H}(S)$ . Since $f(S)>|F|$ , we have $\pi(S)\leq\tau(|F|)$ . But $S$ is a component of $H-F$ and not $G-F$ , which yields a contradiction. $\hfill\blacktriangleleft$

Our intent with Examples 1.2 and 1.3 is to illustrate that $\mathsf{CR}\text{-}{f}\text{-}\mathsf{NDP}$ can be used to model some interesting problems. The choice of the $\tau$ and/or $\pi$ functions can of course impact our ability to solve the LP-relaxation $(\text{{CRLP}}_{f,G})$ efficiently.

4 Structure of feasible CR- $𝒇$ -NDP solutions: a decomposition result

We now prove our decomposition result, showing that $\mathsf{CR}\text{-}{f}\text{-}\mathsf{NDP}$ can be reduced to ${f}\text{-}\mathsf{NDP}$ with suitably-defined weakly-supermodular cut-requirement functions. Recall that the base cut-requirement function $f$ is weakly supermodular (and symmetric, normalized), but the cut-requirement function $g^{\mathsf{CR}\text{-}{f}\text{-}\mathsf{NDP}}$ underlying $\mathsf{CR}\text{-}{f}\text{-}\mathsf{NDP}$ need not be. Given $x\in\mathbb{R}^{E}$ and $S\subseteq V$ , we use $x^{S}$ to denote the restriction of $x$ to edges in $S$ , i.e., the vector $(x_{e})_{e\in E(S)}\in\mathbb{R}^{E(S)}$ .

Theorem 4.1 (Decomposition result).

There is a partition $V_{1},V_{2},\ldots,V_{k}$ of $V$ and weakly-supermodular, symmetric, and normalized functions $f_{i}:2^{V_{i}}\mapsto\mathbb{Z}$ such that the following hold.

(a)

$F\subseteq E$ is a feasible solution to $\mathsf{CR}\text{-}{(f,G)}\text{-}\mathsf{NDP}$ iff $F\supseteq\delta_{G}(V_{i})$ and $F(V_{i})$ is a feasible solution to ${(f_{i},G[{V_{i}}])}\text{-}\mathsf{NDP}$ for all $i\in[k]$ .
(b)

$x\in\mathbb{R}^{E}$ is feasible to $(\text{{CRLP}}_{f,G})$ iff for all $i\in[k]$ , we have $x_{e}=1$ for all $e\in\delta_{G}(V_{i})$ , and $x^{V_{i}}$ is feasible to $(\text{{NDP}}_{f_{i},G[{V_{i}}]})$ .
(c)

$x$ is an extreme-point solution to $(\text{{CRLP}}_{f,G})$ iff for all $i\in[k]$ , we have $x_{e}=1$ for all $e\in\delta_{G}(V_{i})$ , and $x^{V_{i}}$ is an extreme-point solution to $(\text{{NDP}}_{f_{i},G[{V_{i}}]})$ .

Before delving into the proof of Theorem 4.1, we state the following immediate corollary of Theorem 4.1 (c), which directly leads to a $2$ -approximation algorithm for $\mathsf{CR}\text{-}{f}\text{-}\mathsf{NDP}$ whenever $(\text{{CRLP}}_{f,G})$ can be solved efficiently.

Corollary 4.2.

Let $\widehat{x}$ be an extreme-point solution to $(\text{{CRLP}}_{f,G})$ . There exists some $e\in E$ for which $\widehat{x}_{e}\geq 1/2$ .

Proof.

By Theorem 4.1 (c), there is a partition of $V$ and ${f}\text{-}\mathsf{NDP}$ -instances defined on each part such that $\widehat{x}$ induces an extreme-point solution in each ${f}\text{-}\mathsf{NDP}$ -instance. By Jain’s result, this implies that in each of these instances, there is some edge $e$ with $\widehat{x}_{e}\geq 1/2$ . $\hfill\blacktriangleleft$

The rest of this section is devoted to the proof of Theorem 4.1. For a set $S\subseteq V$ , define its deficiency $\operatorname{def}(S):=f(S)-|\delta_{G}(S)|$ . We use $\operatorname{def}_{f,G}(S)$ (or $\operatorname{def}_{f,E}(S)$ ) when we want to make the cut-requirement function and graph (or edge-set) explicit. By Lemma 2.1 (b), $\operatorname{def}(S)$ is weakly supermodular; also, it is symmetric (and normalized). We say that $S$ is a small cut (or more explicitly a small- $(f,G)$ -cut) if $\operatorname{def}(S)>0$ . Clearly, if there is no small cut, then $\mathsf{CR}\text{-}{f}\text{-}\mathsf{NDP}$ becomes equivalent to ${f}\text{-}\mathsf{NDP}$ . Our chief insight and key structural result is that if there is a small cut, then we can simplify the $\mathsf{CR}\text{-}{f}\text{-}\mathsf{NDP}$ instance and move to smaller $\mathsf{CR}\text{-}{f}\text{-}\mathsf{NDP}$ instances, by “splitting” the instance along a suitable small cut (Theorem 4.5). By repeating this operation, we eventually obtain an instance with no small cuts, which leads to Theorem 4.1. The splitting operation relies on the following modification of $f$ .

Definition 4.3.

Let $\emptyset\neq S\subsetneq V$ . Recall that $\overline{S}:=V-S$ . Let $Z=\delta_{G}(S)$ . Define the function $f_{S}:2^{S}\mapsto\mathbb{Z}$ , which we call the restriction of $f$ to $S$ , as follows.

f_{S}(T)=\begin{cases}0;&\text{if $T=\emptyset$ or $T=S$}\\ \max\bigl\{f(T)-|\delta_{Z}(T)|,f(T\cup\overline{S})-|\delta_{Z}(T\cup% \overline{S})|\bigr\}&\text{otherwise}\end{cases}\qquad\forall T\subseteq S.

The intuition here is that for $T\subseteq S$ , $f_{S}(T)$ is a lower bound on the residual requirement that needs to be met from $\delta_{G[{S}]}(T)$ given that we pick all edges of $Z$ . Note that since $f$ and $|\delta_{Z}(.)|$ are symmetric, $f(T\cup\overline{S})-|\delta_{Z}(T\cup\overline{S})|=f(S-T)-|\delta_{Z}(S-T)|$ , and so $f_{S}$ is the symmetric, normalized version of of the residual requirement function $f-|\delta_{Z}(\cdot)|$ .

In the splitting operation, we pick a small cut $A$ of maximum deficiency, and move to $\mathsf{CR}\text{-}{f}\text{-}\mathsf{NDP}$ instances on the smaller graphs $G[{A}]$ , and $G[{\overline{A}}]$ obtained by restricting $f$ to $A$ , and restricting $f$ to $\overline{A}$ respectively (Theorem 4.5). Lemma 4.4 states some basic properties of the restriction of $f$ . Part (b) will be quite useful in proving that the splitting operation maintains feasibility, and part (a) allows us to repeat the splitting operation on the smaller instances. For a set $S\subseteq V$ , and set $F\subseteq E$ of edges, we use $F(S)$ to denote the edges of $F$ with both ends in $S$ .

Lemma 4.4.

Let $\emptyset\neq S\subsetneq V$ . Let $f_{S}$ be the restriction of $f$ to $S$ . Let $\delta_{G}(S)\subseteq F\subseteq E$ .

(a)

$f_{S}$ is weakly supermodular, symmetric, and normalized.
(b)

Let $\emptyset\neq T\subsetneq S$ . Then, $\operatorname{def}_{f_{S},F(S)}(T)=\max\bigl\{\operatorname{def}_{f,F}(T),% \operatorname{def}_{f,F}(T\cup\overline{S})\bigr\}$ .

Proof.

Let $Z=\delta_{G}(S)$ . Define $f^{\prime}:2^{V}\mapsto\mathbb{R}$ by $f^{\prime}(T):=f(T)-|\delta_{Z}(T)|$ . Then, $f^{\prime}$ is weakly supermodular and symmetric (Lemma 2.1 (b)).

For part (a), we can proceed in two ways. As noted earlier, $f_{S}$ is the symmetric, normalized version $f^{\prime}$ , so part (a) follows from Lemma 2.1 (a). Alternatively, observe that $f_{S}$ is the projection of $f^{\prime}$ onto $S$ with respect to $\mathcal{C}:=\{\emptyset,\overline{S}\}$ , which is closed under set intersections, unions, differences, and complements with respect to $V-S$ . So by Lemma 2.1 (c), we obtain that $f_{S}$ is weakly supermodular and symmetric. Also, $f_{S}$ is normalized by definition.

For part (b), the stated equality follows by simply plugging in $f_{S}$ , and noting that for $Y\in\{T,T\cup\overline{S}\}$ , we have $|\delta_{F}(Y)|=|\delta_{F(S)}(T)|+|\delta_{Z}(Y)|$ . $\hfill\blacktriangleleft$

Theorem 4.5 (Splitting along a small cut).

Suppose that there is some small cut. Let $A\subseteq V$ be a maximum-deficiency cut. Note that $\operatorname{def}(A)>0$ and $\emptyset\neq A\subsetneq V$ .

(a)

$F\subseteq E$ is a feasible solution to $\mathsf{CR}\text{-}{(f,G)}\text{-}\mathsf{NDP}$ iff $F\supseteq\delta_{G}(A)$ , $F(A)$ is a feasible solution to $\mathsf{CR}\text{-}{(f_{A},G[{A}])}\text{-}\mathsf{NDP}$ , and $F(\overline{A})$ is a feasible solution to $\mathsf{CR}\text{-}{(f_{\overline{A}},G[{\overline{A}}])}\text{-}\mathsf{NDP}$ .
(b)

$x\in\mathbb{R}_{+}^{E}$ is feasible to $(\text{{CRLP}}_{f,G})$ iff $x_{e}=1$ for all $e\in\delta_{G}(A)$ , $x^{A}$ is feasible to $(\text{{CRLP}}_{f_{A},G[{A}]})$ , and $x^{\overline{A}}$ is feasible to $(\text{{CRLP}}_{f_{\overline{A}},G[{\overline{A}}]})$ .

Proof.

Part (a) can be seen as the special case of part (b), where $x$ is integral. We prove part (a) here, as the proof is somewhat (notational) simpler. For notational simplicity, let $(f_{1},G_{1},F_{1})=\bigl(f_{A},G[{A}],F(A)\bigr)$ and $(f_{2},G_{2},F_{2})=\bigl(f_{\overline{A}},G[{\overline{A}}],F(\overline{A})\bigr)$ . Let $Z=\delta_{G}(A)$ .

The “only if” direction follows easily from the definition of the restriction of $f$ . Let $F$ be feasible to $\mathsf{CR}\text{-}{(f,G)}\text{-}\mathsf{NDP}$ . Since $A$ is a small cut, we must have $F\supseteq Z$ . Consider any $\emptyset\neq T\subsetneq A$ . Since $F$ is feasible, we have $|\delta_{F}(T)|\geq\min\bigl\{f(T),|\delta_{G}(T)|\bigr\}$ , which implies that $|\delta_{F_{1}}(T)|\geq\min\bigl\{f(T)-|\delta_{Z}(T)|,|\delta_{G_{1}}(T)|\bigr\}$ . Similarly, we have $|\delta_{F}(T\cup\overline{A})|\geq\min\bigl\{f(T\cup\overline{A}),|\delta_{G}% (T\cup\overline{A})|\bigr\}$ , so $|\delta_{F_{1}}(T)|\geq\min\bigl\{f(T\cup\overline{A})-|\delta_{Z}(T\cup% \overline{A})|,|\delta_{G_{1}}(T)|\bigr\}$ . Combining the inequalities, and using the definition of restriction, we obtain that $|\delta_{F_{1}}(T)|\geq\min\bigl\{f_{1}(T),|\delta_{G_{1}}(T)|\bigr\}$ . Since $T$ was arbitrary, this shows that $F_{1}$ is feasible to $\mathsf{CR}\text{-}{(f_{1},G_{1})}\text{-}\mathsf{NDP}$ .

A symmetric argument shows that $F_{2}$ is a feasible solution to $\mathsf{CR}\text{-}{(f_{2},G_{2})}\text{-}\mathsf{NDP}$ .

Conversely, suppose that $F\supseteq\delta_{G}(A)$ , $F_{1}=F(A)$ is a feasible solution to $\mathsf{CR}\text{-}{(f_{1},G_{1})}\text{-}\mathsf{NDP}$ , and $F_{2}=F(\overline{A})$ is a feasible solution to $\mathsf{CR}\text{-}{(f_{2},G_{2})}\text{-}\mathsf{NDP}$ . Recall that $Z=\delta_{G}(A)$ . Consider any $\emptyset\neq T\subsetneq V$ . Lemma 4.4 (b) can be used to readily argue that if $T\subseteq A$ or $T\subseteq\overline{A}$ , then the constraint for set $T$ in $\mathsf{CR}\text{-}{(f,G)}\text{-}\mathsf{NDP}$ is satisfied. We show this for $T\subseteq A$ ; a symmetric argument applies for $T\subseteq\overline{A}$ . If $T$ is a small- $(f_{1},G_{1})$ -cut, then $F_{1}\supseteq\delta_{G_{1}}(T)$ . Since $F\supseteq Z$ , this implies that $F\supseteq\delta_{G}(T)$ . Otherwise, we have $\operatorname{def}_{f_{1},F_{1}}(T)\leq 0$ , so by Lemma 4.4 (b), we have that $\operatorname{def}_{f,F}(T)\leq\operatorname{def}_{f_{1},F_{1}}(T)\leq 0$ . Thus, we always have $|\delta_{F}(T)|\geq\min\bigl\{f(T),|\delta_{G}(T)|\bigr\}$ .

Now consider $T$ such that $T\cap A,T\cap\overline{A}\neq\emptyset$ . We exploit the weak supermodularity of $\operatorname{def}_{f,F}$ , and that $A$ has maximum deficiency, to bound $\operatorname{def}_{f,F}(T)$ in terms of the deficiency of sets that do not cross $A$ , and thus show that the constraint for $T$ is satisfied. We have
$\begin{split}\operatorname{def}_{f,F}(T)+\operatorname{def}_{f,F}(A)&\leq% \operatorname{def}_{f,F}(T\cap A)+\operatorname{def}_{f,F}(T\cup A)=% \operatorname{def}_{f,F}(T\cap A)+\operatorname{def}_{f,F}(\overline{A}-T)\ \ % \text{or}\\ \operatorname{def}_{f,F}(T)+\operatorname{def}_{f,F}(A)&\leq\operatorname{def}% _{f,F}(A-T)+\operatorname{def}_{f,F}(T-A)\end{split}$

where in the first inequality we also use the fact that $\operatorname{def}_{f,F}$ is symmetric. In both cases, we have $\operatorname{def}_{f,F}(T)+\operatorname{def}_{f,F}(A)\leq\operatorname{def}_% {f,F}(X)+\operatorname{def}_{f,F}(Y)$ where $X\subseteq A$ , $Y\subseteq\overline{A}$ and $\delta_{G}(T)\subseteq\delta_{G}(X)\cup\delta_{G}(Y)\cup Z$ . As shown previously, for $S\in\{X,Y\}$ , we have $|\delta_{F}(S)|\geq\min\bigl\{f(S),|\delta_{G}(S)|\bigr\}$ , or equivalently, $\operatorname{def}_{f,F}(S)\leq\max\bigl\{0,\operatorname{def}_{f,G}(S)\bigr\}$ . Note that $\operatorname{def}_{f,F}(A)=\operatorname{def}_{f,G}(A)>0$ since $F\supseteq\delta_{G}(A)$ . Since $A$ is a maximum-deficiency small cut, this also implies that $\operatorname{def}_{f,F}(A)\geq\operatorname{def}_{f,F}(S)$ for $S\in\{X,Y\}$ : we have $\operatorname{def}_{f,F}(S)\leq\max\bigl\{0,\operatorname{def}_{f,G}(S)\bigr\}% \leq\max\bigl\{0,\operatorname{def}_{f,G}(A)\bigr\}=\operatorname{def}_{f,F}(A)$ .

If both $X$ and $Y$ are small- $(f,G)$ -cuts, then we are done since then we have that $F\supseteq\delta_{G}(X)\cup\delta_{G}(Y)\cup Z\supseteq\delta_{G}(T)$ . Otherwise, since $\operatorname{def}_{f,F}(A)\geq\max\bigl\{\operatorname{def}_{f,F}(X),% \operatorname{def}_{f,F}(Y)\bigr\}$ , we have $\operatorname{def}_{f,F}(T)\leq\min\bigl\{\operatorname{def}_{f,F}(X),% \operatorname{def}_{f,F}(Y)\bigr\}\leq 0$ , since at least one of $X, Y$ is not a small- $(f,G)$ -cut. $\hfill\blacktriangleleft$

Proof of Theorem 4.1.

Parts (a) and (b) follow easily by induction on the number of nodes, using parts (a) and (b) of Theorem 4.5. Consider part (a). The base case is when there is no small- $(f,G)$ -cut, in which case, we have $V_{1}=V$ , and $f_{1}=f$ . Otherwise, let $A=\operatorname{argmax}_{S\subseteq V}\operatorname{def}_{f,G}(S)$ . Since $f_{A}$ and $f_{\overline{A}}$ are weakly-supermodular, we can recurse and induct on $\mathsf{CR}\text{-}{(f_{A},G[{A}])}\text{-}\mathsf{NDP}$ and $\mathsf{CR}\text{-}{(f_{\overline{A}},G[{\overline{A}}])}\text{-}\mathsf{NDP}$ instances, both of which have fewer nodes, to obtain partitions of $A$ and $\overline{A}$ ; we combine these to obtain $V_{1},\ldots,V_{k}$ . Theorem 4.5 (a) and the induction hypothesis then readily yield part (a) here. The only thing to note is that since the induction hypothesis yields $F\supseteq\delta_{G[{A}]}(V_{i})$ for a part $V_{i}\subseteq A$ , and $F\supseteq\delta_{G}(A)$ by Theorem 4.5 (a), we have $F\supseteq\delta_{G}(V_{i})$ . Similarly, $F\supseteq\delta_{G}(V_{i})$ for any part $V_{i}\subseteq\overline{A}$ .

Part (b) follows similarly from Theorem 4.5 (b). Part (c) follows from part (b), because it is not hard to see, using part (b), that any convex combination of feasible solutions to $(\text{{CRLP}}_{f,G})$ yields a convex combination of feasible $(\text{{NDP}}_{f_{i},G[{V_{i}}]})$ -solutions, and vice versa. $\hfill\blacktriangleleft$

One may wonder if the ${(f_{i},G[{V_{i}}])}\text{-}\mathsf{NDP}$ -instances in the decomposition of Theorem 4.1 can be specified more directly or succinctly. In the full version, we prove some properties of the decomposition given by its proof, which as a consequence, enable one to do so. But we need our splitting approach to argue why this succinct description fulfills the properties in Theorem 4.1. The properties we establish also imply that the decomposition in Theorem 4.1 can be computed efficiently given suitable algorithmic access to the base cut-requirement function $f$ .

5 Algorithmic implication: LP-relative $2$ -approximation algorithm

We now exploit the decomposition result stated in Theorem 4.1, and Corollary 4.2, to obtain a $2$ -approximation algorithm. We assume that we have a separation oracle for $(\text{{CRLP}}_{f,G})$ , which implies that we can efficiently find an extreme-point optimal solution to $(\text{{CRLP}}_{f,G})$ and any LP that arises in a subsequent iteration after fixing some $x_{e}$ variables to $1$ (Fact 2.2).

Algorithm 1 CRNDP-Alg.

$\blacktriangleright$ Remark 5.1.

The collection of small cuts does not change across iterations; that is, $S$ is a small- $(f,G)$ -cut iff it is a small- $(f^{\prime},G^{\prime})$ -cut in some other iteration. This is because, for any $S\subseteq V$ , we change $|\delta_{G^{\prime}}(S)|$ and $f^{\prime}(S)$ by the same amount in every iteration. In the first iteration, we have $\widehat{x}_{e}=1$ for every $e\in\delta_{G}(S)$ and every small cut $S$ , and so $\delta_{G^{\prime}}(S)=\emptyset$ in any subsequent iteration. So we do not have any constraints for small cuts in subsequent iterations, and this causes problems with uncrossing tight constraints. Nevertheless, we are able to argue, due to our decomposition result, that there is always some edge with $\widehat{x}_{e}\geq 1/2$ .

Theorem 5.2.

Let $\mathit{OPT}$ denote the optimal value of $(\text{{CRLP}}_{f,G})$ . Algorithm CRNDP-Alg returns a feasible $\mathsf{CR}\text{-}{f}\text{-}\mathsf{NDP}$ -solution $F\subseteq E$ such that $c(F)\leq 2\cdot\mathit{OPT}$ .

Proof.

By Corollary 4.2, at least one edge gets added to $F$ in every iteration, so the algorithm terminates in at most $|E|$ iterations. The cost bound follows by induction on the number of iterations to termination. The base case is trivial. Suppose $F=Z_{1}\cup F^{\prime}$ , where $F^{\prime}$ is the solution found in subsequent iterations for the instance $\mathsf{CR}\text{-}{(f^{\prime},G^{\prime})}\text{-}\mathsf{NDP}$ . Let $\mathit{OPT}^{\prime}$ be the optimal solution to $(\text{{CRLP}}_{G^{\prime},f^{\prime}})$ . Then, by induction, we have $c(F_{1})\leq 2\cdot\mathit{OPT}^{\prime}$ and $\mathit{OPT}^{\prime}\leq\sum_{e\in E^{\prime}}c_{e}\widehat{x}_{e}$ , since $(\widehat{x}_{e})_{e\in E^{\prime}}$ is a feasible solution to $(\text{{CRLP}}_{f^{\prime},G^{\prime}})$ . We also have $c(Z_{1})\leq 2\cdot\sum_{e\in Z_{1}}c_{e}\widehat{x}_{e}$ . Therefore, $c(F)\leq 2c^{T}\widehat{x}=2\cdot\mathit{OPT}$ . $\hfill\blacktriangleleft$

Since $(\text{{CRLP}}_{f^{\mathsf{SNDP}},G})$ admits a polytime separation oracle (Lemma 2.3), we obtain the following result as a corollary.

Theorem 5.3.

There is a $2$ -approximation algorithm for $\mathsf{CR}\text{-}\mathsf{SNDP}$ .

6 Hardness result

We now show that cut-relative $\mathsf{SNDP}$ and path-relative $\mathsf{SNDP}$ are APX-hard, even when the base $\mathsf{SNDP}$ instance involves only one $s$ - $t$ pair, by showing that the $k$ -edge connected subgraph ( $k\text{-}\mathsf{ECSS}$ ) problem can be cast as a special case of these problems. (This hints at the surprising amount of modeling power of {cut, path}- relative $\mathsf{SNDP}$ .) Previously, even NP-hardness of path-relative $\mathsf{SNDP}$ in the $s$ - $t$ case was not known.

Let $\bigl(G=(V,E),\{c_{e}\}_{e\in E}\bigr)$ be an instance of $k\text{-}\mathsf{ECSS}$ . We may assume that $G$ is at least $k$ -edge connected, i.e., $|\delta_{G}(S)|\geq k$ for all $\emptyset\neq S\subsetneq V$ , as otherwise there is no feasible solution (and this can be efficiently detected).

Consider the following path-relative $\mathsf{SNDP}$ instance. We add a source $s$ and sink $t$ , and edges $s v, v t$ of cost $0$ , for all $v\in V$ . Let $G^{\prime}=(V^{\prime},E^{\prime})$ denote this graph. The base- $\mathsf{SNDP}$ instance asks for $(k+n)$ -edge connectivity between $s$ and $t$ , where $n=|V|$ . That is, the base cut-requirement function $f$ is given by $f(S^{\prime})=k+n$ if $S^{\prime}\subseteq V^{\prime}$ is an $s$ - $t$ cut, and $f(S^{\prime})=0$ otherwise. We show that path-relative $\mathsf{SNDP}$ and cut-relative $\mathsf{SNDP}$ are actually equivalent in this case, and that they encode $k\text{-}\mathsf{ECSS}$ on the graph $G$ .

Theorem 6.1.

$H\subseteq E^{\prime}$ is a feasible solution to the above {cut, path}-relative $\mathsf{SNDP}$ instance $\iff$ $H\supseteq\delta_{G^{\prime}}(s)\cup\delta_{G^{\prime}}(t)$ and $H(V)$ is a feasible $k\text{-}\mathsf{ECSS}$ -solution for $G$ . Hence, this {cut,path}-relative $\mathsf{SNDP}$ instance is the same as $k\text{-}\mathsf{ECSS}$ on the graph $G$ .

Proof.

Recall that we are assuming that $G$ is (at least) $k$ -edge connected. The following observation will be handy. The only small cuts in $G^{\prime}$ are $\{s\}$ and $\{t\}$ (and their complements). For any other $s$ - $t$ cut $S^{\prime}\subseteq V^{\prime}$ , taking $S=S^{\prime}\cap V$ , we have that $\emptyset\neq S\subsetneq V$ . So we have $|\delta_{G^{\prime}}(S^{\prime})|=|\delta_{G}(S)|+|S|+|V-S|\geq k+n$ .

$\Leftarrow$ direction.

We argue that $H$ is feasible for cut-relative $\mathsf{SNDP}$ , which also implies that it is feasible for path-relative $\mathsf{SNDP}$ . Clearly, $H$ covers both small cuts. For any other $s$ - $t$ cut $S^{\prime}\subseteq V^{\prime}$ , taking $S=S^{\prime}\cap V$ , we have $|\delta_{H}(S^{\prime})|\geq|\delta_{H(V)}(S)|+|S|+|V-S|\geq k+n$ , since $H(V)$ is a feasible $k\text{-}\mathsf{ECSS}$ -solution for $G$ .

$\Rightarrow$ direction.

Suppose that $H$ is feasible for path-relative $\mathsf{SNDP}$ . If there is some edge $sv\notin H$ , then consider the fault-set $F=\delta_{G^{\prime}}(s)-\{sv\}$ . Then $H-F$ clearly has no $s$ - $t$ path, since $\delta_{H-F}(s)=\emptyset$ . But $G^{\prime}-F$ has an $s$ - $t$ path $s v, v t$ . So we must have $H\supseteq\delta_{G^{\prime}}(s)$ . A similar argument shows that $H\supseteq\delta_{G^{\prime}}(t)$ .

We next argue that $|\delta_{H}(S^{\prime})|\geq n+k$ for every $s$ - $t$ cut $S^{\prime}$ for which $\emptyset\neq S:=S^{\prime}\cap V\subsetneq V$ . This is equivalent to showing that $|\delta_{H(V)}(S)|\geq k$ , since $|\delta_{H}(S^{\prime})\cap\delta_{G^{\prime}}(s)|+|\delta_{H}(S^{\prime})\cap% \delta_{G^{\prime}}(t)|=n$ . Assume that $s\in S^{\prime}$ without loss of generality. Suppose $|\delta_{H(V)}(S)|<k$ . Since $|\delta_{G}(S)|\geq k$ , there is some edge $uv\in\delta_{G}(S)-\delta_{H(V)}(S)$ . Suppose $u\in S$ . Consider the fault-set $F=\delta_{H(V)}(S)\cup\{sw:w\in V-S\}\cup\{wt:w\in S\}$ . Then $|F|<k+n$ and $H-F$ has no $s$ - $t$ path, since we have constructed $F$ to ensure that $\delta_{H-F}(S^{\prime})=\emptyset$ . However, $G-F$ has an $s$ - $t$ path: $s u, u v, v t$ . This contradicts that $H$ is feasible for path-relative $\mathsf{SNDP}$ .

So we have shown both that $H(V)$ is feasible $k\text{-}\mathsf{ECSS}$ solution for $G$ , and that $H$ is feasible for cut-relative $\mathsf{SNDP}$ .

Since the cost of the edges in $E^{\prime}-E$ is $0$ , the above {cut, path}-relative $\mathsf{SNDP}$ instance is exactly the same as $k\text{-}\mathsf{ECSS}$ on the graph $G$ . $\hfill\blacktriangleleft$

7 Non-equivalence of path-relative SNDP and cut-relative SNDP

We consider the same graph and base $\mathsf{SNDP}$ instance as in Fig. 1. The graph is reproduced below for convenience, and recall that the base cut-requirement function models $s$ - $t$ $2$ -edge connectivity: so $f(S)=2$ if $S$ is an $s$ - $t$ cut, and $f(S)=0$ otherwise.

A feasible solution to path-relative $\mathsf{SNDP}$ is given by the edge-set $H_{1}=\{su,uw,sw,wt\}$ , which has cost $3$ . (This is in fact an optimal solution to path-relative $\mathsf{SNDP}$ .)

However, $H_{1}$ is not feasible for cut-relative $\mathsf{SNDP}$ . This is because, we require $\delta_{H}(\{s,u,w\})\geq\min\{2,3\}=2$ in any feasible $\mathsf{CR}\text{-}\mathsf{SNDP}$ solution $H$ . Moreover, one can infer that any feasible $\mathsf{CR}\text{-}\mathsf{SNDP}$ -solution must include all but one of the edges from $\{su,uw,sw,sv,vw\}$ . This is because for any $F\subseteq\{su,uw,sw,sv,vw\}$ with $|F|=2$ , one can verify that there is an $s$ - $t$ cut $S$ such that $|\delta_{G}(S)|=3$ and $F\subseteq\delta_{G}(S)$ ; so $|\delta_{G-F}(S)|\leq 1$ , which implies that there is no feasible solution that excludes $F$ . A feasible $\mathsf{CR}\text{-}\mathsf{SNDP}$ -solution must also include the edge $w t$ , so the optimal value for cut-relative $\mathsf{SNDP}$ is $4$ .

While cut-relative $\mathsf{SNDP}$ and path-relative $\mathsf{SNDP}$ are not in general equivalent, they are closely related. Dinitz et al. [9] showed (see Lemma A.1 in [9]) that one can give a cut-based formulation for path-relative $\mathsf{SNDP}$ , where $H$ is feasible iff $|\delta_{H}(S)|\geq\min\bigl\{f(S),|\delta_{G}(S)|\}$ for every $S\subseteq V$ such that $G[{S}]$ and $G[{V^{\prime}-S}]$ are connected graphs, where $V^{\prime}\subseteq V$ is the vertex-set of the component containing $S$ . That is, we require the cut-constraints of $\mathsf{CR}\text{-}\mathsf{SNDP}$ to hold for a suitable collection of node-sets (as opposed to all node-sets in $\mathsf{CR}\text{-}\mathsf{SNDP}$ ). This immediately implies that $\mathsf{CR}\text{-}\mathsf{SNDP}$ and path-relative $\mathsf{SNDP}$ are equivalent when the underlying graph is a (capacitated) complete graph. Also, as mentioned earlier, path-relative $k\text{-}\mathsf{ECSS}$ and cut-relative $k\text{-}\mathsf{ECSS}$ are equivalent [8].

References

[1] A. Agrawal, Phil Klein, and R. Ravi. When trees collide: An approximation algorithm for the generalized Steiner problem on networks. SIAM Journal on Computing, 24:440–456, 1995. doi:10.1137/S0097539792236237.
[2] Ishan Bansal. A global analysis of the primal-dual method for edge-augmentation problems. In Proceedings of the 26th IPCO, pages 58–71, 2025. doi:10.1007/978-3-031-93112-3_5.
[3] Ishan Bansal, Joseph Cheriyan, Logan Grout, and Sharat Ibrahimpur. Improved approximation algorithms by generalizing the primal-dual method beyond uncrossable functions. Algorithmica, 86(8):2575–2604, 2024. doi:10.1007/S00453-024-01235-2.
[4] Nikhil Bansal, Rohit Khandekar, Jochen Könemann, Viswanath Nagarajan, and Britta Peis. On generalizations of network design problems with degree bounds. Mathematical Programming, 141(1-2):479–506, 2013. doi:10.1007/S10107-012-0537-8.
[5] Nikhil Bansal, Rohit Khandekar, and Viswanath Nagarajan. Additive guarantees for degree-bounded directed network design. SIAM Journal on Computing, 39(4):1413–1431, 2009. doi:10.1137/080734340.
[6] Sylvia C. Boyd, Joseph Cheriyan, Arash Haddadan, and Sharat Ibrahimpur. Approximation algorithms for flexible graph connectivity. Mathematical Programming, 204:493–516, 2024. doi:10.1007/S10107-023-01961-5.
[7] Chandra Chekuri and Rhea Jain. Approximation algorithms for network design in non-uniform fault models. In Proceedings of the 50th ICALP, pages 36:1–36:20, 2023. doi:10.4230/LIPICS.ICALP.2023.36.
[8] Michael Dinitz, Ama Koranteng, and Guy Kortsarz. Relative survivable network design. In Proceedings of the 25th APPROX, pages 41:1–41:19, 2022. doi:10.4230/LIPICS.APPROX/RANDOM.2022.41.
[9] Michael Dinitz, Ama Koranteng, Guy Kortsarz, and Zeev Nutov. Improved approximations for relative survivable network design. In Proceedings of the 21st WAOA, pages 190–204, 2023. doi:10.1007/978-3-031-49815-2_14.
[10] M. Goemans and D. Williamson. A general approximation technique for constrained forest problems. SIAM J. on Computing, 24:296–317, 1995. doi:10.1137/S0097539793242618.
[11] M. Goemans and D. Williamson. The primal-dual method for approximation algorithms and its application to network design problems. In Dorit Hochbaum, editor, Approximation algorithms for NP-hard problems, chapter 4. PWS Publishing Company, 1996.
[12] Michel X. Goemans, Andrew V. Goldberg, Serge A. Plotkin, David B. Shmoys, Éva Tardos, and David P. Williamson. Improved approximation algorithms for network design problems. In Proceedings of the 5th SODA, pages 223–232, 1994. URL: http://dl.acm.org/citation.cfm?id=314464.314497.
[13] M.X. Goemans. Minimum bounded-degree spanning trees. In Proceedings of the 47th FOCS, pages 273–282, 2006.
[14] Martin Grötschel, Lászlo Lovász, and Lex Schrijver. Geometric algorithms and combinatorial optimization. Algorithms and Combinatorics 2. Springer, 1993.
[15] Kamal Jain. A factor 2 approximation algorithm for the generalized Steiner network problem. Combinatorica, 21(1):39–60, 2001. doi:10.1007/S004930170004.
[16] N. Klein and N. Olver. Thin trees for laminar families. In Proceedings of the 64th FOCS, 2023.
[17] Lap Chi Lau, Seffi Naur, Mohammad Salavatipour, and Mohit Singh. Survivable network design with degree or order constraints. SIAM Journal on Computing, 39(3):1062–1087, 2009. doi:10.1137/070700620.
[18] Lap Chi Lau, R. Ravi, and Mohit Singh. Iterative methods in combinatorial optimization. Cambridge University Press, 2011.
[19] Mohit Singh and Lap Chi Lau. Approximating minimum bounded degree spanning trees to within one of optimal. In Proceedings of the 39th STOC, pages 661–670. ACM, 2007. doi:10.1145/1250790.1250887.
[20] David P. Williamson, Michel X. Goemans, Milena Mihail, and Vijay V. Vazirani. A primal-dual approximation algorithm for generalized steiner network problems. Combinatorica, 15(3):435–454, 1995. doi:10.1007/BF01299747.

[bib.bib1] [1] A. Agrawal, Phil Klein, and R. Ravi. When trees collide: An approximation algorithm for the generalized Steiner problem on networks. SIAM Journal on Computing, 24:440–456, 1995. doi:10.1137/S0097539792236237.

[bib.bib2] [2] Ishan Bansal. A global analysis of the primal-dual method for edge-augmentation problems. In Proceedings of the 26th IPCO, pages 58–71, 2025. doi:10.1007/978-3-031-93112-3_5.

[bib.bib3] [3] Ishan Bansal, Joseph Cheriyan, Logan Grout, and Sharat Ibrahimpur. Improved approximation algorithms by generalizing the primal-dual method beyond uncrossable functions. Algorithmica, 86(8):2575–2604, 2024. doi:10.1007/S00453-024-01235-2.

[bib.bib4] [4] Nikhil Bansal, Rohit Khandekar, Jochen Könemann, Viswanath Nagarajan, and Britta Peis. On generalizations of network design problems with degree bounds. Mathematical Programming, 141(1-2):479–506, 2013. doi:10.1007/S10107-012-0537-8.

[bib.bib5] [5] Nikhil Bansal, Rohit Khandekar, and Viswanath Nagarajan. Additive guarantees for degree-bounded directed network design. SIAM Journal on Computing, 39(4):1413–1431, 2009. doi:10.1137/080734340.

[bib.bib6] [6] Sylvia C. Boyd, Joseph Cheriyan, Arash Haddadan, and Sharat Ibrahimpur. Approximation algorithms for flexible graph connectivity. Mathematical Programming, 204:493–516, 2024. doi:10.1007/S10107-023-01961-5.

[bib.bib7] [7] Chandra Chekuri and Rhea Jain. Approximation algorithms for network design in non-uniform fault models. In Proceedings of the 50th ICALP, pages 36:1–36:20, 2023. doi:10.4230/LIPICS.ICALP.2023.36.

[bib.bib8] [8] Michael Dinitz, Ama Koranteng, and Guy Kortsarz. Relative survivable network design. In Proceedings of the 25th APPROX, pages 41:1–41:19, 2022. doi:10.4230/LIPICS.APPROX/RANDOM.2022.41.

[bib.bib9] [9] Michael Dinitz, Ama Koranteng, Guy Kortsarz, and Zeev Nutov. Improved approximations for relative survivable network design. In Proceedings of the 21st WAOA, pages 190–204, 2023. doi:10.1007/978-3-031-49815-2_14.

[bib.bib10] [10] M. Goemans and D. Williamson. A general approximation technique for constrained forest problems. SIAM J. on Computing, 24:296–317, 1995. doi:10.1137/S0097539793242618.

[bib.bib11] [11] M. Goemans and D. Williamson. The primal-dual method for approximation algorithms and its application to network design problems. In Dorit Hochbaum, editor, Approximation algorithms for NP-hard problems, chapter 4. PWS Publishing Company, 1996.

[bib.bib12] [12] Michel X. Goemans, Andrew V. Goldberg, Serge A. Plotkin, David B. Shmoys, Éva Tardos, and David P. Williamson. Improved approximation algorithms for network design problems. In Proceedings of the 5th SODA, pages 223–232, 1994. URL: http://dl.acm.org/citation.cfm?id=314464.314497.

[bib.bib13] [13] M.X. Goemans. Minimum bounded-degree spanning trees. In Proceedings of the 47th FOCS, pages 273–282, 2006.

[bib.bib14] [14] Martin Grötschel, Lászlo Lovász, and Lex Schrijver. Geometric algorithms and combinatorial optimization. Algorithms and Combinatorics 2. Springer, 1993.

[bib.bib15] [15] Kamal Jain. A factor 2 approximation algorithm for the generalized Steiner network problem. Combinatorica, 21(1):39–60, 2001. doi:10.1007/S004930170004.

[bib.bib16] [16] N. Klein and N. Olver. Thin trees for laminar families. In Proceedings of the 64th FOCS, 2023.

[bib.bib17] [17] Lap Chi Lau, Seffi Naur, Mohammad Salavatipour, and Mohit Singh. Survivable network design with degree or order constraints. SIAM Journal on Computing, 39(3):1062–1087, 2009. doi:10.1137/070700620.

[bib.bib18] [18] Lap Chi Lau, R. Ravi, and Mohit Singh. Iterative methods in combinatorial optimization. Cambridge University Press, 2011.

[bib.bib19] [19] Mohit Singh and Lap Chi Lau. Approximating minimum bounded degree spanning trees to within one of optimal. In Proceedings of the 39th STOC, pages 661–670. ACM, 2007. doi:10.1145/1250790.1250887.

[bib.bib20] [20] David P. Williamson, Michel X. Goemans, Milena Mihail, and Vijay V. Vazirani. A primal-dual approximation algorithm for generalized steiner network problems. Combinatorica, 15(3):435–454, 1995. doi:10.1007/BF01299747.

Tight Guarantees for Cut-Relative Survivable Network Design via a Decomposition Technique

Abstract

Keywords and phrases:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

Funding:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

Definition 1.1.

Modeling power.

Example 1.2.

Example 1.3.

1.1 Our contributions

Technical contributions and overview.

Other related work.

2 Preliminaries and notation

Properties of cut-requirement functions.

Lemma 2.1.

Proof.

2.1 LP-relaxation for CR-𝒇-NDP

Fact 2.2 (Ellipsoid method [14]).

Lemma 2.3.

Proof.

Extreme-point solution to (CRLPf,G) not defined by a laminar family

𝒙^ cannot be defined via a laminar family.

3 Modeling power of CR-𝒇-NDP

Theorem 3.1.

Proof.

Theorem 3.2.

Proof.

4 Structure of feasible CR-𝒇-NDP solutions: a decomposition result

Theorem 4.1 (Decomposition result).

Corollary 4.2.

Proof.

Definition 4.3.

Lemma 4.4.

Proof.

Theorem 4.5 (Splitting along a small cut).

Proof.

Proof of Theorem 4.1.

5 Algorithmic implication: LP-relative 𝟐-approximation algorithm

▶ Remark 5.1.

Theorem 5.2.

Proof.

Theorem 5.3.

6 Hardness result

Theorem 6.1.

Proof.

⇐ direction.

⇒ direction.

7 Non-equivalence of path-relative SNDP and cut-relative SNDP

References

2.1 LP-relaxation for CR- $𝒇$ -NDP

Extreme-point solution to $(\text{{CRLP}}_{f,G})$ not defined by a laminar family

$\widehat{x}$ cannot be defined via a laminar family.

3 Modeling power of CR- $𝒇$ -NDP

4 Structure of feasible CR- $𝒇$ -NDP solutions: a decomposition result

5 Algorithmic implication: LP-relative $2$ -approximation algorithm

$\blacktriangleright$ Remark 5.1.

$\Leftarrow$ direction.

$\Rightarrow$ direction.