Protecting the Connectivity of a Graph Under Non-Uniform Edge Failures
Abstract
We study the problem of guaranteeing the connectivity of a given graph by protecting or strengthening edges. Herein, a protected edge is assumed to be robust and will not fail, which features a non-uniform failure model. We introduce the -Steiner-Connectivity Preservation problem where we protect a minimum-cost set of edges such that the underlying graph maintains -edge-connectivity between given terminal pairs against edge failures, assuming at most unprotected edges can fail. We design polynomial-time exact algorithms for the cases where and are small and approximation algorithms for general values of and . Additionally, we show that when both and are part of the input, even deciding whether a given solution is feasible is -complete. This hardness also carries over to Flexible Network Design, a research direction that has gained significant attention. In particular, previous work focuses on problem settings where either or is constant, for which our new hardness result now provides justification.
Keywords and phrases:
Network Design, Edge Failures, Graph Connectivity, Approximation AlgorithmsFunding:
Zhenwei Liu: Research supported in part by NSFC (No. 12271477).Copyright and License:
![[Uncaptioned image]](x1.png)
2012 ACM Subject Classification:
Mathematics of computing Combinatorial optimization ; Theory of computation Design and analysis of algorithmsEditors:
Olaf Beyersdorff, Michał Pilipczuk, Elaine Pimentel, and Nguyễn Kim ThắngSeries and Publisher:

1 Introduction
In today’s interconnected world, the robustness of infrastructures is crucial, particularly in the face of potential disruptions. This applies to road networks, communication grids, and electrical systems alike, where the ability to maintain functionality despite failures is paramount. Resilience in critical infrastructures requires the incorporation of redundancy to withstand unforeseen challenges. Survivable Network Design (SND) addresses the fundamental need of ensuring not just connectivity but robust connectivity. It goes beyond the conventional concept of linking two entities by recognizing the need for multiple, resilient connections.
Beyond its practical applications, SND is a fundamental problem in combinatorial optimization and approximation algorithms. In its classical setting, we are given a graph with edge costs and connectivity requirements for each vertex pair . The goal is to find a minimum-cost subset of edges such that is -connected for each , i.e., in there are many edge-disjoint paths for each vertex pair . This means that and are still connected in after the deletion of any edges of . SND is -hard and the current best approximation factor of is achieved by Jain’s famous iterative rounding algorithm [32]. It is a long-standing open question whether this factor can be improved, even for many special cases of SND.
Instead of building a new network from scratch, many real-world applications as well as the research community consider augmentation problems, in which we are already given some network, and the task is to robustify the network to withstand failures. The most common model is to increase the connectivity of a given network by adding more links [22, 25]. However, adding new links to a real-world network may be costly or even impractical.
This motivates the investigation of the problem of increasing the connectivity of a network by protecting or strengthening edges, as has been proposed by Abbas et al. [1] in a practical context. In this paper, we formally introduce the problem -Steiner-Connectivity Preservation (-SCP): Given an undirected graph , possibly with parallel edges, nonnegative costs and terminal pairs . The task is to identify a minimum-cost set of edges such that for any edge set with , there are edge-disjoint paths between any terminal pair in . In other words, the task is to protect a minimum-cost subset of the edges such that, no matter which unprotected edges from are removed from , there are still edge-disjoint paths between any terminal pair. We refer to the special case with a single terminal pair by ---Connectivity Preservation (-stCP) and the other extreme case in which each pair of vertices is a terminal pair as -Global-Connectivity Preservation (-GCP). Using this notion, Abbas et al. [1] considered -GCP and proposed to start from a minimum spanning tree and remove unnecessary edges, which does not admit bounded approximation factors. Zhang et al. [44] used mixed-integer linear programming to solve -GCP and -SCP. Bienstock and Diaz [12] considered a special case of -SCP, the all-pair connectivity among a set of terminals, and showed a polynomial-time algorithm for and the -hardness for .
The distinction between protected and unprotected edges has a similar flavor as the -Flexible Network Design (-FND) problem [3, 2, 13, 8, 6, 17, 7, 9]. The input is an edge-weighted undirected graph together with a set of terminal pairs, where the edges are either safe or unsafe. The goal is to find a minimum-cost subgraph such that any terminal pair remains -edge-connected after the failure of any unsafe edges. Also here different versions have been studied, e.g., -GFND, the global connectivity version (each pair of vertices is a terminal pair) or -stFND, the - version (only one terminal pair). In contrast to their model, in our setting we strengthen existing edges rather than building a network from scratch. For , -SCP reduces to -FND. Given an instance of -SCP, we construct an instance of -FND as follows. We use the same underlying graph but replace each edge by two parallel edges: one unsafe edge of cost zero and one safe edge with cost equal to the cost of protecting the edge in the instance of -SCP. Since the unsafe edges have cost zero, we can assume that any feasible solution includes all unsafe edges. Then, a feasible solution to -FND can be transformed into a feasible solution to -SCP with the same cost by protecting the selected safe edges and vice versa. For , however, we are not aware of any reduction from -SCP to -FND.
1.1 Our Contribution
In this paper, we study Connectivity Preservation problems in terms of algorithms, complexity, and approximability.
The -Steiner-Connectivity Preservation problem is -hard if is part of the input: When is sufficiently large, say, larger than , any feasible solution to -SCP includes at least one edge in any terminal-separating cut (precise definitions are given in Section 2). Hence, it is equivalent to Steiner Forest, which is -hard [11]. Similarly, -GCP is -hard for any , as it contains the minimum -edge-connected spanning subgraph problem [39] as a special case when is sufficiently large. We strengthen this by showing that -GCP is also -hard when is part of the input.
Motivated by the problem hardness, we first study cases when or is small. We obtain polynomial-time exact algorithms for -SCP for any and -SCP as well as a polynomial-time exact algorithm for -GCP. We emphasize that -SCP generalizes -GCP and hence any algorithm for -SCP also works for -GCP.
Theorem 1 (summarized).
There are polynomial-time exact algorithms for -Steiner-Connectivity Preservation for any and -Steiner-Connectivity Preservation. Furthermore, there is a polynomial-time exact algorithm for -Global-Connectivity Preservation.
The first result for -SCP is quite easily obtained by observing that a solution is only feasible if every edge contained in some terminal-separating cut of size at most is protected.
The polynomial-time algorithm for -SCP is more involved and relies on a decomposition of terminal-separating cuts of size . We reduce the problem to the case in which is assumed to be -edge-connected. Then, it remains to protect one edge in each terminal-separating cut of size . To do so, we decompose the problem into subproblems that consist either of a -edge-connected component or a cycle that can be solved independently.
The polynomial-time algorithm for -GCP is the most involved exact algorithm. We first show that we can assume without loss of generality that is -edge-connected, which reduces the problem to selecting a minimum-cost set of edges containing at least edges from each -edge-cut. Equivalently, we select a maximum-weight set of edges such that we pick at most edge from each -edge-cut. Using the well-known tree-representation of minimum cuts [20], we model this problem as a multi-commodity flow problem on a tree: given a tree and a set of weighted paths on the tree, find a maximum weighted subset of paths that are pairwise edge-disjoint, which was first introduced in [28] for the unweighted case. We solve the weighted problem via dynamic programming, which might be of independent interest.
We complement our exact algorithms for small and with hardness and approximation results for more general cases. For -SCP, if both and are part of the input, we show that there is no polynomial-time algorithm verifying the feasibility of any given solution, unless , even in the case of --connectivity. This rules out an -approximation algorithm for any . Our technique is based on a reduction from -Clique on -regular graphs. Note that the corresponding solution verifying problems of -stCP and -stFND are essentially the same: given sets of protected (resp. safe) and unprotected (resp. unsafe) edges, decide whether there is an --cut that has no more than edges and has less than protected (resp. safe) edges. Hence, the hardness of verifying a solution also carries over to ---Flexible Network Design and justifies why previous work on this problem only discusses the cases where either or is constant [3, 17].
Theorem 2.
When both and are part of the input, verifying the feasibility of a solution to ---Connectivity Preservation or ---Flexible Network Design is -complete, even in perfect graphs. Hence, they do not admit an -approximation for any unless .
On the algorithmic side, if is a constant, we can enumerate all “bad” edge sets whose removal destroy the -edge-connectivity. Since any feasible solution intersects with or hits these “bad” sets, it reduces to the hitting set problem and admits a -approximation. Then we focus on the case where is a constant. We first give a -approximation for -SCP and extend it to -SCP based on a primal-dual framework [43, 29]. In the framework, we iteratively protect one more edge in each critical cut (precise definition follows), which is very similar to the problem -SCP. We obtain the following result.
Theorem 3.
There is a polynomial-time -approximation algorithm for -Steiner-Connectivity Preservation when is a constant.
The global connectivity problem -GCP has more symmetric structure, which enables us to remove the requirement of being constant. Hence, the above result directly carries over to this case without the assumption on . In addition, we design a different set-cover based augmentation process. This algorithm relies on the fact that there is only a polynomial number of critical cuts to be augmented, which is not true for -SCP. Combining the two algorithms, we obtain the following result.
Theorem 4.
There is a polynomial-time -approximation algorithm for -Global-Connectivity Preservation.
We obtain further results for special cases by showing reductions to known problems. Since the Augmenting Small Cuts problem [8] generalizes -Global-Connectivity Preservation, we obtain a 5-approximation building on [37]. Further, we show that ---Connectivity Preservation is equivalent to the Minimum Shared Edge problem; formally defined in Section 4. This reduction implies, due to earlier work, a fixed-parameter tractable (FPT) algorithm parameterized by if the graph is undirected [23] and an -algorithm (slice-wise polynomial) for directed graphs [5]. Further, for directed graphs the equivalence of the two problems implies a strong inapproximability bound of , unless [38]. Since ---Connectivity Preservation is a special case of ---Flexible Network Design, namely, -Flexible Network Design with only a single terminal pair, this strong hardness bound also holds for -stFND, where the best-known lower bound on the approximation ratio is unless [3].
1.2 Related Work
The -Steiner-Connectivity Preservation problem generalizes many well-known problems from survivable network design (SND), which itself generalizes a collection of connectivity problems such as the minimum spanning tree problem, the Steiner tree and forest problem, or the minimum -edge-connected spanning subgraph problem (-ECSS).
Many special cases of SND remain -hard. This includes many augmentation problems, where typically the task is to increase the connectivity of a graph by at least . If the set of edges to be added is unrestricted, the problem can be solved even in near-linear time [22, 15], whereas the problem is -hard otherwise [25, 34]. Well-studied such problems include the Connectivity Augmentation problem [40, 42] and the Tree Augmentation problem [41, 14].
A problem of similar flavor was introduced by Adjiashvili, Stiller and Zenklusen [4], who initiated the study of highly non-uniform failure models, called bulk-robustness. Therein, a family of edge sets is given and the goal is to find a minimum-cost spanning subgraph such that is connected for any . They proposed an -approximation algorithm for a generalized matroid setting. They also studied an --connectivity variant and obtained an -approximation algorithm, where . Recently, Chekuri and Jain [18] considered the connectivity between multiple vertex pairs and achieved an -approximation algorithm.
The aforementioned Flexible Network Design problem can be viewed as a problem between survivable network design and bulk-robustness, as it divides the edge set into safe and unsafe edges and only unsafe edges can fail simultaneously. Since the work by Adjiashvili, Hommelsheim and Mühlenthaler [2] for -GFND, there has been a lot of work on -GFND. Most research focused on the case where either or is a small constant. Boyd et al. [13] obtained -approximation for -GFND, a -approximation for -GFND and -approximation for -GFND. Very recently, Bansal et al. [9] showed an improved -approximation algorithm for -GFND. We refer to [8, 6, 17, 9] for a collection of results, including constant approximation for -GFND, -approximation for -GFND and -approximation for -GFND for even . Parallel to -GFND, Adjiashvili et al. [3] considered the --connectivity variant, to which some results in [17] translate.
Another closely related problem is the Capacitated -Connected Subgraph problem (Cap--ECSS) [16]. In this problem, we are given an undirected graph with edge costs and edge capacities . The goal is to find a minimum-cost spanning subgraph in which the capacity of any cut is at least . Boyd et al. [13] pointed out that -GFND (hence also -GCP) can be reduced to Cap--ECSS by setting the capacity of safe and unsafe edges to and , respectively. For Cap--ECSS, the best-known approximation algorithms are -approximation by Chakrabarty et al. [16] and -approximation by Bansal et al. [9].
2 Preliminaries: Notation, Cut Formulation, Hardness
Graph notation.
For an undirected graph and a vertex set , we use to denote the set of edges with exactly one endpoint in . We write if the underlying graph is clear from the context. An edge cut is a subset of edges such that has at least connected components. If , we call a bridge. Further, if there is some terminal pair such that and are in different connected components in , we say is terminal-separating. Let . We use the notation of to denote the graph obtained from by contracting , i.e., by deleting and identifying . Let be some subgraph of . We slightly abuse the notation of contraction and use to represent the graph obtained from by contracting all edges in . Let . We use to denote the graph . Similarly, we define .
An equivalent cut formulation.
Given an instance of -Steiner-Connectivity Preservation, we define as the set of critical (terminal-separating) cuts. Our problem can be equivalently formulated as the following cut-based integer program, in which we have to cover all critical cuts:
min | |||||
s.t. | (CutIP) | ||||
Proposition 5.
(CutIP) characterizes the feasible solutions of -SCP. Moreover, a solution is feasible if and only if any critical cut contains at least protected edges.
Proof.
We show that an edge set is a feasible solution if and only if for any vertex set , . Consider a feasible solution and suppose that there is some with and . Then, after removing no more than edges from , the remaining graph has a cut with less than edges. Further, this cut separates some terminal pair. Thus, is not a feasible solution.
Suppose for all we have . We show that after removing at most unprotected edges, the remaining graph is still -edge-connected between any terminal pair. For any cut with , there are at least remaining edges since we remove at most edges. Fix any terminal pair and any edge set with . We show that for any --cut , which implies -edge-connectivity between . If , then . If , then by the constraint of (CutIP). Thus it also holds that .
Given a partial solution , we call a cut safe (w.r.t. ) if it is not critical or it contains at least edges in . Otherwise, we call it unsafe.
NP-hardness.
In addition to the aforementioned complexity observations, we now show that -GCP is -hard, even in the unweighted setting where we protect a minimum number of edges. Observe that any spanning tree of is a feasible solution, which implies . However, we show that it is -complete to distinguish whether or , by a reduction from the largest bond problem [21]. Therein, we are given an undirected graph and an integer . A bond is an edge set represented by for some with both and being connected. The task is to decide whether there is a bond of size at least .
We outline the idea for the hardness proof as follows. Given an instance of the largest bond problem, we reduce it to an instance of -GCP using the same graph with . If there is a bond of size at least , then protecting a spanning tree of and is feasible, as the cut is not critical, which implies . If , then the protected edges in the optimal solution induce multiple connected components. We can find a bond of size at least by contracting the connected components induced by the protected edges and computing the minimum cut of the resulting graph.
Theorem 6.
Unweighted -Global-Connectivity Preservation is -hard.
Proof.
Given an instance of the largest bond problem, we construct an instance of -Global-Connectivity Preservation using the same graph with .
If there is a bond of size at least , then the optimal solution value of the -Global-Connectivity Preservation instance is no more than , as we can simply protect a spanning tree of and a spanning tree of ), which exist since is a bond.
If there is no bond of size at least , we claim that the optimal solution of the instance of -Global-Connectivity Preservation must be a spanning tree using edges. Suppose the optimal solution is not a spanning tree, and it consists of connected components , . After contracting , the graph has to be -edge-connected, by feasibility. Let be this graph. Note that in any graph there must be a minimum cut such that consists of exactly connected component. Hence, there is also such a minimum cut in and this cut has size at least , as is -edge-connected. But then corresponds to a bond of size at least in the original graph, a contradiction.
3 Exact Algorithms for small
In this section we design three polynomial-time exact algorithms for different cases depending on and , i.e., we prove Theorems 7, 10, and 17, which together imply Theorem 1.
3.1 -Steiner-Connectivity Preservation
To give some intuition, we first show a simple algorithm for -Steiner-Connectivity Preservation. By Proposition 5, an instance is feasible if and only if there is no terminal-separating cut of size less than . Hence, from now on we assume the instance is feasible.
The set of critical cuts is given by . Hence, any feasible solution must contain all edges of any critical cut. Therefore, the only inclusion-wise minimal solution consists of all edges in any terminal-separating cut of size and it remains to find all such edges. To this end, we assign different capacities to protected edges and unprotected edges such that any safe cut has a strictly larger capacity than that of any unsafe cut. The algorithm works as follows.
Algorithm 1.
Let be the current partial solution; initially . In each iteration, we set the capacity of the edges to for all and otherwise. For every terminal pair , we solve the Minimum --Cut Problem using standard polynomial-time algorithms. If we find a terminal-separating cut of capacity less than , then this defines an unsafe critical cut and we protect all edges in it, i.e., we add to and repeat. If each terminal-separating cut has capacity at least , output .
Theorem 7.
Algorithm 1 is a polynomial-time exact algorithm for -Steiner-Connectivity Preservation.
Proof.
Algorithm 1 runs obviously in polynomial time. Note that we can decide the feasibility of the given instance by enumerating terminal pairs and checking whether there is a terminal-separating cut of size less than . We now assume there is none and the instance is feasible.
Let be a partial solution. We claim that the capacity function in Algorithm 1 distinguishes safe and unsafe cuts with respect to . Specifically, a cut is unsafe if and only if its capacity is strictly less than . By the feasibility of the instance, any terminal-separating cut has at least edges. Let be any terminal-separating cut. If or , then the capacity of is at least . If and , then its capacity is smaller than . Thus we can find an unsafe terminal-separating cut by enumerating terminal pairs and computing a minimum - cut with respect to the capacity function. By the preceding discussion, Algorithm 1 finds an optimum solution in polynomial time.
3.2 -Steiner-Connectivity Preservation
In this subsection we present a polynomial-time algorithm for -Steiner-Connectivity Preservation. The set of critical cuts is . Hence, we distinguish between bridges and -edge-cuts. We first show that we can reduce to the case that the input graph is -edge-connected.
Given any bridge of , if separates some terminal pair, any feasible solution has to include . In this case, we pay and consider the new instance defined by . If there is no such terminal pair, then any inclusion-wise minimal feasible solution should not include , which implies that we can delete and consider the two connected components of individually. As a result, we can assume that the input graph is -edge-connected. Note that if the graph is -edge-connected, then there is no critical cut and we are done.
Given a terminal-separating -edge-cut of , at least one of and has to be contained in any feasible solution. However, deciding which edge to protect is non-trivial. We show how to further decompose our instance into smaller and independent instances according to the following structural lemma. See Figure 1(a) for an illustration.
Lemma 8.
Given an undirected graph which is -edge-connected but not -edge-connected, and a -edge-cut of , there is a polynomial-time algorithm to decompose into disjoint -edge-connected subgraphs such that after contracting the resulting graph forms a cycle and belong to this cycle.
Proof.
Consider the graph , which is connected but not -edge-connected. Let arise from by contracting each -edge-connected component. Note that is isomorphic to a tree. Since is -edge-connected, must be a path. Further, connects the two end-vertices of the path and is a path edge ( is a bridge of ). Let the nodes of the path be and for let be the -edge-connected component represented by , respectively. We conclude that forms a cycle and belong to this cycle.
Given a decomposition as in Lemma 8, we claim that the problem reduces to solving certain subproblems defined by (plus some additional pseudo-edge for each component) and the subproblem restricted to the cycle . To do so, we view our problem as finding a minimum-cost edge set that intersects all -edge-cuts. Observe that any inclusion-wise minimal -edge-cut is either two edges on the cycle , or two edges in for some . Hence, we can solve our problem by solving the subproblem defined by -edge-cuts on the cycle and the subproblems defined by -edge-cuts in each component separately.
The subproblem is a Steiner Forest problem on a cycle. This follows from the observation that any feasible solution must contain a path consisting of only protected edges between each terminal pair. We can solve the min-cost Steiner Forest problem on a cycle by enumerating which cycle-edge is not in the optimum solution and breaking the cycle into a path. On a path, the solution is the union of the unique paths between the terminal pairs. Then, we recursively solve the subproblems in each . However, we cannot simply recurse on since a -edge-cut of may not be a -edge-cut of . Instead, we recourse on a new graph obtained by adding a zero-cost edge to . This edge connects the two vertices that are incident to the edges of , which represents the connection in between these vertices via the cycle . We formalize this idea in the following lemma (See Figure 1(b)).
Lemma 9.
Given a decomposition as in Lemma 8, an optimum solution to -SCP can be obtained by combining optimum solutions of the following subproblems:
-
(i)
protect a minimum-cost edge set that intersects with any terminal-separating -edge-cut on the cycle, and
-
(ii)
for each , let be the two vertices incident to the two edges in the cycle. Solve the problem on with . Keep the terminal pairs with both terminals in . For terminal pairs with , replace it with .
Proof.
We first show that given any feasible solution of , the corresponding edges of on each subproblem is a feasible solution for the subproblem. For the cycle subproblem (ii) this is trivial. For any subproblem , we show is a feasible solution. Observe that any -edge-cut in cannot contain the edge since is -edge-connected. Thus, must also be a -edge-cut in . If separates some terminal pair in , so does it in , which implies . Therefore, each terminal-separating -edge-cut of is safe.
Given feasible solutions of the subproblems, we show how to obtain a feasible solution of without increasing the cost. Let be the edges protected in the subproblems except the new edges . Thus, the cost of is at most the sum of the cost of the solutions to the individual subproblems. It remains to argue that is feasible for . Let be any terminal-separating -edge-cut of . If is on the cycle, by the feasibility of the subproblem on the cycle, . If is in for some , must also be a terminal-separating -edge-cut of . Thus . We conclude that is feasible for .
Algorithm 2.
We first protect terminal-separating bridges, contract them, and consider the -edge-connected components separated by non-terminal-separating bridges individually. This reduces to the case that is -edge-connected. Then, as long as we find a terminal-separating -edge-cut (which is the only type of critical cut), we decompose the problem into a subproblem on a cycle and a collection of subproblems in smaller -edge-connected components. Then we recursively solve the individual subproblems. The decomposition stops either if is -edge-connected (and hence we are done as there is no critical cut) or each component on the cycle consists of a single vertex, i.e., if is a cycle. The cycle case is solved by enumerating which edge of the cycle is not contained in an optimum solution and then solving a Steiner Forest problem on a path where the optimal solution is trivial. Among all such solutions, we output the one with minimum cost.
Theorem 10.
Algorithm 2 is a polynomial-time exact algorithm for -Steiner-Connectivity Preservation.
We remark that Bienstock and Diaz [12] studied a special case of -SCP. They showed that it is -hard when and they conjectured the -hardness for .
Interestingly, -Global-Connectivity Preservation admits an easier algorithm. We view the problem as finding a minimum-cost edge set hitting all -edge-cuts, which reduces to a special case of Minimum Weighted Vertex Cover. Therein, each edge of corresponds to a vertex in the Vertex Cover instance and there is an edge between two vertices and if and only if forms a -edge-cut in . The Vertex Cover instance has a special structure with each connected component being a complete graph. To see this observe that, if both and are -edge-cuts, then is also a -edge-cut ([35, Lemma 2.37]). The optimal vertex cover solution in a complete graph is trivial: select all vertices except the largest-weighted one. We conclude with the following result.
Lemma 11.
The greedy algorithm that selects from each -edge-cut the cheaper edge solves -Global-Connectivity Preservation.
3.3 -Global-Connectivity Preservation when
We now present a polynomial-time algorithm for -GCP. Note that for all other , our previous results imply a polynomial-time algorithm for -GCP. We outline our algorithm as follows. By Proposition 5, we can assume the input graph to be -edge-connected, as otherwise, the instance is infeasible. Further, a feasible solution contains at least two edges in each -edge-cut and in each -edge-cut. We first show that if there is some -edge-cut, it is equivalent to solving two smaller independent instances (Lemma 12). Hence, we can assume that the input graph is -edge-connected. Then we represent all the -edge-cuts using a standard tree representation [20, 30] and it remains to solve a weighted multi-commodity flow problem on the tree (introduced formally later, Lemma 14). Finally, we solve the weighted multi-commodity flow problem via dynamic programming (Lemma 16).
Suppose is not -edge-connected and there is some -edge-cut , i.e., consists of connected components . Let with and , with and (see Figure 2). We create two new instances: on where is an edge with zero cost and on , where has zero cost. We show that it suffices to solve independently and combine their solutions to get a solution to the original instance.
Lemma 12.
.
Proof.
Given a feasible solution of , we show that and are feasible solutions for and , respectively, implying and . We show feasibility for ; the feasibility for is analogous. It suffices to show that for any critical cut in , at least edges are protected. Consider any critical cut of . If does not contain the new edge , then it is also a critical cut of and therefore this cut is safe. Hence, we assume that contains the new edge and let . Note that might not exist if . We show that is a critical cut in . Consider and observe that is a bridge in , as is a cut in . Hence, and are only connected in via the edge . This means that also in , any path connecting and must use . Hence, is a bridge in and therefore is a critical cut in . Thus contains at least protected edges, which implies contains at least protected edge. Since is protected, has at least protected edges and is safe.
On the other hand, given solutions and of and , respectively, we show that is feasible for , implying and . Let be any critical cut of . Without loss of generality, we assume that is inclusion-wise minimal, i.e., it does not contain any smaller critical cut. We distinguish the following three cases. First, assume that . Then, must also be an edge cut of and therefore is safe. The case is analogous. For the second case, we assume that the first case does not apply and further assume that . Hence, either or . Without loss of generality assume . Observe that is a critical edge cut in and is a critical edge cut in . Further, by feasibility of and , the only edge in and at least one of the two edges in must be protected, which implies contains at least protected edges and is safe. In the third and final case, we assume that none of the previous cases apply and further assume that contains either or . Any cut containing both and is safe, as both are protected in . Without loss of generality assume . We claim that either or . Otherwise, contains one edge in and one edge in . Observe that is a -edge-cut of , which contradicts the fact that is inclusion-wise minimal. If , then similar to the first part of this proof one can show that is a cut in . Hence, and therefore, , as . The case is analogous and hence this concludes the proof.
By repeating the above process, we end up with a -edge-connected graph. The following tree representation gives us a clear structure about all the -edge-cuts and it can be computed in near-linear time [30].
Definition 13 (Tree representation of min cuts [20]).
Let be an undirected graph and suppose the capacity of its minimum cut is an odd number . There is a polynomial-time algorithm that constructs a rooted tree together with a (not necessarily surjective) mapping . Further, there is a one-to-one correspondence between any -edge-cut of and as follows. For any , let be the subtree of beneath and let . Then for any tree edge , defines a -edge-cut of . For any -edge-cut of , there is some tree edge such that .
Given this tree representation, we show now that our problem -Global-Connectivity Preservation reduces to the weighted multi-commodity flow problem on a tree. This problem is defined as follows: given a tree , a set of paths on the tree and a weight function , find a subset of pairwise edge-disjoint paths with maximum total weight.
Lemma 14.
When the input graph is -edge-connected, -Global-Connectivity Preservation reduces to the weighted multi-commodity flow problem on a tree.
Proof.
A solution is feasible if and only if it contains at least edges in each -edge-cut. Equivalently, for each -edge-cut at most one edge is unprotected. We consider this complement problem in which we want to find a set of maximum-weight edges such that each -edge-cut contains at most one edge of . We use the standard tree representation [20] of all the -edge-cuts of , in which each -edge-cut of the original graph is represented by an edge in the tree. Given a tree representation and , define as the path on between and and let the weight of be the cost of . Observe that every -edge-cut containing corresponds to a tree edge on and vice versa. Therefore, a solution is feasible if and only if the set of paths are pairwise edge-disjoint. Hence finding the optimal reduces to finding a set of edge-disjoint paths on , maximizing the total weight, which is the weighted multi-commodity flow problem.
Remark 15.
We can prove that Lemma 14 holds more generally for any even : If is -edge-connected, -GCP reduces to the weighted multi-commodity flow problem on a tree for any even . However, to solve -GCP using this reduction, we need to reduce the problem to the case where is -edge-connected, which remains unclear for .
Garg et al. [28] considered an unweighted version of multi-commodity flow problem on a tree and obtained an exact polynomial-time greedy algorithm. However, their arguments do not extend to the weighted case. We design a dynamic program for the weighted version.
Lemma 16.
The weighted multi-commodity flow problem on a tree can be solved in polynomial time.
Proof.
We root the tree at an arbitrary vertex . Without loss of generality, we assume there is no path that consists of only one vertex since the selected paths have to be only edge-disjoint. For any vertex , let be the subtree rooted at vertex . For any tree edge where is closer to the root, we use to represent the subtree for short. Define the subproblem in the subtree as follows: From the set of paths completely contained in , select a maximum-weight subset of paths that are pairwise edge-disjoint. Let be the optimal value of . We define and for each analogously. We only show how to compute ; the computation of is similar.
Fix some vertex and consider the subproblem . If is a leaf, then . Otherwise, let be the children of . Let be the set of paths intersecting . We say a path occupies the subtree if it intersects . Our first observation is that each subtree can be occupied by at most one selected path, as otherwise the edge is contained in multiple selected paths, which is infeasible. Since a path in can occupy either two subtrees for some or only one subtree for some , we reduce the problem to an instance of Maximum Weighted Matching. For , we create an auxiliary graph as follows. For each with , we create a vertex corresponding to the subtree and a dummy vertex . For each path in , if it occupies and for some , we create an edge between and . If it only occupies one subtree , we create an edge between and . We also create an extra edge between and which represents the case where no selected path occupies . It is not hard to see that there is a one-to-one correspondence between a feasible choice over in and a matching on the auxiliary graph . It remains to properly set the weights of the edges of such that a maximum-weight matching in corresponds to an optimum solution for . To do so, we observe that for a given fixed feasible choice over , it remains to solve a collection of subproblems represented by or for some and combine their optimal solutions. Formally, let be a path in where , . Assume occupies two subtrees of , say, and . The case only occupies one subtree of follows analogously. Suppose we have selected . Then it is still feasible to select paths completely contained in and , respectively, as long as they do not intersect . This implies that the subproblems on and can be decomposed into and , respectively. See Figure 3 for an example. Hence, the gain of selecting is the sum of the optimal values of these subproblems plus the weight of itself. That is, we set . For the extra edge between and , which represents no selected path occupies , we set its weight to . It now easily follows that , which can be solved in polynomial time using algorithms for Maximum Weighted Matching [26].
Theorem 17.
There is a polynomial-time exact algorithm for -Global-Connectivity Preservation.
4 Approximation Algorithms for large or
In this section we provide approximation algorithms and hardness results for large and .
4.1 Approximation for the cases with
We present a primal-dual algorithm for -Steiner-Connectivity Preservation. Consider the corresponding linear programming relaxation of (CutIP) and its dual:
s.t. | ||||
s.t. | ||||
Algorithm 3.
We start from a dual solution and maintain a partial solution which is the current protected edge set. At the beginning, . We increase the dual variables iteratively and add edges to whose corresponding dual constraints become tight. In each iteration, we pick some with and increase . Such a vertex set can be found by enumerating terminal pairs and checking whether there is an --cut of value less than with respect to the following capacity function: set the capacity of to if and to , otherwise. We increase until for some edge , the dual constraint is tight. Then we add to and move to the next iteration until is a feasible solution, which is the case if any terminal-separating cut has a capacity of at least w.r.t. the above capacity function.
To bound the cost of , we have
Theorem 18.
Algorithm 3 is a polynomial-time -approximation algorithm for -Steiner-Connectivity Preservation.
The global connectivity variant -GCP has more symmetry since we do not need to distinguish whether an edge cut is terminal-separating. By exploiting the special structure of the family , Bansal et al. [8] obtained a primal-dual -approximation algorithm for the Augmenting Small Cuts problem, which generalizes -GCP. Recently, the factor has been reduced to [37] and [6] via refined analysis.
Theorem 19 (follows from [8, 6]).
There is a polynomial-time -approximation algorithm for -Global-Connectivity Preservation.
Finally, we consider ---Connectivity Preservation. We show that this problem is equivalent to the undirected Minimum Shared Edge problem: We are given a graph with edge weights and two specified vertices . The task is to find - paths with the minimum total weight of shared edges. Here, an edge is shared if it is contained in at least paths.
Proposition 20.
An edge set is a feasible solution to -stCP if and only if there are --paths such that any edge shared by at least two paths belongs to .
Proof.
To show necessity, we construct a graph with a capacity function on the edges, where the capacity of any edge is if , and otherwise. Since is a feasible solution, by Proposition 5 the capacity of any - cut is at least . Thus, there exist --paths such that edges shared by at least two paths belong to .
As for the sufficiency, suppose we have --paths that only share edges in . We claim that the shared edges form a feasible solution of -stCP. For each cut of size at most , at least one edge must be shared by two paths and this edge is in . Thus, every cut with satisfies . By Proposition 5, is a feasible solution.
Lemma 21.
An edge set is an inclusion-wise minimal solution to ---Connectivity Preservation if and only if there are --paths such that the shared edges are exactly .
We conclude that -stCP is equivalent to the Minimum Shared Edge Problem. Hence, Lemma 21 and the results of [23, 5, 38] imply the following.
Theorem 22.
When parameterized by , -stCP admits an FPT algorithm for undirected graphs and an XP algorithm for directed graphs. Furthermore, -stCP on directed graphs admits no -approximation, unless .
4.2 Extension for larger
Before presenting algorithms for more general cases, we argue that -SCP is quite hopeless when both and are part of the input. Indeed, if this is the case, there is no polynomial-time algorithm that verifies feasibility of any given solution unless .
By Proposition 5, a given protected edge set is infeasible if and only if there is a terminal-separating cut such that and . We define and study the complexity of the following ()-bicriteria --cut problem: Given an undirected graph with two specified vertices and a subset of edges protected, decide whether there is an --cut such that the number of protected edges in the cut is at most () and the total number of edges in the cut is at most () and. Recall that in the ---Flexible Network Design problem, verifying the feasibility of a solution can be formulated as follows. Given an undirected graph with safe and unsafe edges, decide whether there are edge-disjoint paths between and after at most failures of unsafe edges. Hence verifying the feasibility is equivalent to the ()-bicriteria --cut problem. We show that the ()-bicriteria --cut problem is -complete, which implies that there is no polynomial-time approximation algorithm for ---Connectivity Preservation or ---Flexible Network Design, unless .
See 2
Proof.
We use a reduction similar to [24] from -Clique on -regular graphs, which is -complete [27]. See Figure 4 for an illustration. In -Clique, we are given an undirected graph and we need to decide whether there is a clique of size . Given an instance of -clique with graph , where is -regular, we construct an instance of the -bicriteria --cut problem as follows. Let . We create vertices corresponding to and vertices corresponding to . In the following, when we say we connect two vertices, then they are connected by an unprotected edge by default. For each , we connect its corresponding vertex to the two vertices corresponding to and . Then we create a vertex and connect it to each vertex in with protected edges. Create an auxiliary clique of size and fix an arbitrary vertex in the clique as . Fix vertices in the clique other than and fully connect them to each vertex in , which results in a complete bipartite subgraph . Let . We claim that has a clique of size if and only if the protected edges form an infeasible solution to the instance of the -bicriteria --cut problem.
For the first direction, suppose has a clique of size . Let include all the vertices in and corresponding to , and the auxiliary clique . We show defines an -bicriteria --cut. In , the only protected edges are those edges between and the vertices corresponding to . Hence there are exactly protected edges. As for , consider the edges between and . Each vertex in contributes and each vertex in contributes . Now consider the edges between and . There are edges incident to , among which do not contribute to . Hence, and is an -bicriteria --cut.
For the other direction, suppose there is an -bicriteria --cut with such that contains at most protected edges. We show that corresponds to the vertices of a clique of size in and contains the edges of this clique. Observe that since there are at most protected edges in . We will show that and . Furthermore, these vertices in have both their neighbors in . Hence defines a clique of size in .
Observe that must include the whole auxiliary clique C, otherwise would exceed . Let and note that . We prove that by considering the following process. Starting from , we add the vertices in one by one to . During the process, does not change since each vertex in is connected to exactly vertices in , vertices in and . Hence . Now starting from , we add the vertices in one by one to . During the process, the only case that adding a vertex decreases (by ) is when both its neighbors are in . Therefore, we have at least vertices in , each having both their neighbors in , since . Hence, , and with the above inequality of we have . Further, for any two vertices in , there is some vertex in connected to both of them, implying that corresponds to the vertices of a clique in . Hence, contains a clique of size .
On the positive side, if is a constant, we can enumerate those edge sets with such that some terminal pair in is not -edge-connected. For each of those sets, we need to protect at least one edge in the set, which reduces to the hitting set problem and admits a -approximation where is the largest size of the sets to be hit [10, 31].
In the following, we extend algorithm for -SCP to -SCP with being a constant. The idea is to start from an empty solution and augment the current solution by iteratively increasing the number of protected edges in each critical cut. Our algorithm consists of phases. In phase , we are given a partial solution satisfying that each critical cut contains at least edges in . We then (approximately) solve the following augmentation problem : Add to a minimum-cost set of edges such that includes at least edges of each critical cut. That is, find a set that includes at least one edge from each critical cut with exactly protected edges in . The augmentation problem is solved similarly to the primal-dual framework for -SCP.
Formally, let . In phase with , we define , i.e., the critical cuts with exactly protected edges. Next, we solve the following problem : find a minimum-cost edge set such that for any . Then we set and go on to the next phase. To solve , we use a primal-dual algorithm based on the following LP to compute a -approximation solution to which is essentially the same as -Steiner-Connectivity Preservation. The approximation ratio is bounded by as the size of a critical cut is at most .
min | ||||||
s.t. | ||||||
The only difference is the process of finding a violating set with respect to some partial solution . However, finding such a violating set is non-trivial. We are only aware of a solution when is a constant, which we present in the following lemma.
Lemma 23.
Given an edge set , there is a polynomial-time algorithm that computes a set such that when is a constant.
Proof.
Since , we have for any . It suffices to find some with . To this end, we guess the edge set . Note that . Further, for each edge in , we guess whether or . Thus the number of possibilities is at most , which is polynomial when is constant. For the edges in , let the set of endpoints in be , and the other endpoints be . It reduces to finding some with , and . This can be achieved by identifying the vertices in and by a new vertex and , respectively, contracting edges in , and computing a minimum - cut in the resulting graph. If the cut has size less than , then this cut belongs to and has edges in . To bound the total cost of the phases of our algorithm, we use the following LP relaxation and its dual for the analysis. The constraints cannot be omitted as we do for . Otherwise, an edge may be “protected” multiple times, which is not allowed.
min | ||||
s.t. | ||||
max | ||||
s.t. | ||||
In the following lemma, we compare the optimal cost of the augmentation problem to the optimal cost of -Steiner-Connectivity Preservation.
Lemma 24.
Given a feasible dual solution of , we can construct a feasible dual solution of -Steiner-Connectivity Preservation such that
Proof.
Let for and for . Let for and for . We claim that forms a feasible dual solution. For any , by definition. For , . Next, we compare the dual objective values of and . We have
By definition of , for any , we have . Thus, we conclude:
See 3
Proof.
The algorithm consists of phases. In phase , we apply Lemma 23 and the primal-dual framework for -SCP to find a -approximation solution for the augmentation problem . By Lemma 24, the cost of in phase is at most . Thus the total cost is at most , where is the -th harmonic number. Using , we obtain the theorem.
For -Global-Connectivity Preservation, we can approximately solve the augmentation problem without requiring to be a constant. Indeed, we reduce finding the critical cuts to finding certain -approximate minimum cuts in , where each edge has a capacity of if and otherwise. These cuts can be enumerated in polynomial time [33, 36].
Algorithm 4.
In phase , we apply the -approximation algorithm from [6]. That is, we compute such that for any , . For phase with , we approximately solve the augmentation problem by reducing it to Set Cover. Here, we view a set as an element in the Set Cover instance and view an edge as a set in the Set Cover instance. We use either the -approximation [19] where is the number of elements to be covered, or the -approximation [10, 31] where is the maximum number of sets in which an element is contained. Note that applying Lemma 24 requires a dual feasible solution, which is fortunately a byproduct of these Set Cover algorithms.
See 4
Proof.
The cost of phase is no more than . For phase with , we apply Set Cover algorithms explicitly. We show that the number of elements to be covered is and we can construct the Set Cover instance in polynomial time. To this end, we assign different capacities to edges in and other edges such that for any , is a -approximate minimum cut with respect to the capacity function. By Karger’s bound [33], the number of -approximate minimum cuts is and we can enumerate them in polynomial time [36]. Formally, let the capacity of edges in be and the capacity of edges in be 1. Given any cut , the capacity of is at least since it either contains at least edges or contains at least edges in . For any , the capacity of is at most . Thus defines a -approximate minimum cut and we can find all the sets in in polynomial time.
Further, in the constructed Set Cover instance, an element is contained in at most sets since for any . Thus, we can compute an augmenting edge set whose cost is where is the dual feasible solution of . Combining it with Lemma 24, we conclude that the algorithm is an -approximation.
5 Conclusion
We examine Connectivity Preservation from two perspectives. For small values of and , we focus on polynomial-time exact algorithms. For large values of and , we show hardness and devise approximation algorithms. Nonetheless, there remain some gaps between cases solvable in polynomial time and NP-hard ones. In particular, it remains open whether -GCP admits any polynomial-time exact algorithm for constant . Another interesting problem is -GCP with being the capacity of the minimum cuts, i.e., finding a minimum-cost edge set that intersects with all the minimum cuts. Note that for the --connectivity variant, this can be tackled via Min-cost Flow techniques.
References
- [1] Waseem Abbas, Aron Laszka, Yevgeniy Vorobeychik, and Xenofon Koutsoukos. Improving network connectivity using trusted nodes and edges. In 2017 American Control Conference (ACC), pages 328–333. IEEE, 2017. doi:10.23919/ACC.2017.7962974.
- [2] David Adjiashvili, Felix Hommelsheim, and Moritz Mühlenthaler. Flexible graph connectivity. Math. Program., 192(1):409–441, 2022. doi:10.1007/S10107-021-01664-9.
- [3] David Adjiashvili, Felix Hommelsheim, Moritz Mühlenthaler, and Oliver Schaudt. Fault-tolerant edge-disjoint s-t paths - beyond uniform faults. In SWAT, volume 227 of LIPIcs, pages 5:1–5:19. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022. doi:10.4230/LIPICS.SWAT.2022.5.
- [4] David Adjiashvili, Sebastian Stiller, and Rico Zenklusen. Bulk-robust combinatorial optimization. Math. Program., 149(1-2):361–390, 2015. doi:10.1007/S10107-014-0760-6.
- [5] Sepehr Assadi, Ehsan Emamjomeh-Zadeh, Ashkan Norouzi-Fard, Sadra Yazdanbod, and Hamid Zarrabi-Zadeh. The minimum vulnerability problem. Algorithmica, 70(4):718–731, 2014. doi:10.1007/S00453-014-9927-Z.
- [6] Ishan Bansal. A global analysis of the primal-dual method for pliable families, 2024. arXiv:2308.15714.
- [7] Ishan Bansal, Joe Cheriyan, Logan Grout, and Sharat Ibrahimpur. Algorithms for 2-connected network design and flexible steiner trees with a constant number of terminals. In APPROX/RANDOM, volume 275 of LIPIcs, pages 14:1–14:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023. doi:10.4230/LIPICS.APPROX/RANDOM.2023.14.
- [8] 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.
- [9] Ishan Bansal, Joseph Cheriyan, Sanjeev Khanna, and Miles Simmons. Improved approximation algorithms for flexible graph connectivity and capacitated network design, 2024. doi:10.48550/arXiv.2411.18809.
- [10] Reuven Bar-Yehuda and Shimon Even. A linear-time approximation algorithm for the weighted vertex cover problem. J. Algorithms, 2(2):198–203, 1981. doi:10.1016/0196-6774(81)90020-1.
- [11] Marshall W. Bern and Paul E. Plassmann. The steiner problem with edge lengths 1 and 2. Inf. Process. Lett., 32(4):171–176, 1989. doi:10.1016/0020-0190(89)90039-2.
- [12] Daniel Bienstock and Nicole Diaz. Blocking small cuts in a network, and related problems. SIAM J. Comput., 22(3):482–499, 1993. doi:10.1137/0222034.
- [13] Sylvia C. Boyd, Joseph Cheriyan, Arash Haddadan, and Sharat Ibrahimpur. Approximation algorithms for flexible graph connectivity. Math. Program., 204(1):493–516, 2024. doi:10.1007/S10107-023-01961-5.
- [14] Federica Cecchetto, Vera Traub, and Rico Zenklusen. Bridging the gap between tree and connectivity augmentation: unified and stronger approaches. In STOC, pages 370–383. ACM, 2021. doi:10.1145/3406325.3451086.
- [15] Ruoxu Cen, Jason Li, and Debmalya Panigrahi. Edge connectivity augmentation in near-linear time. In STOC, pages 137–150. ACM, 2022. doi:10.1145/3519935.3520038.
- [16] Deeparnab Chakrabarty, Chandra Chekuri, Sanjeev Khanna, and Nitish Korula. Approximability of capacitated network design. Algorithmica, 72(2):493–514, 2015. doi:10.1007/S00453-013-9862-4.
- [17] Chandra Chekuri and Rhea Jain. Approximation algorithms for network design in non-uniform fault models. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023.
- [18] Chandra Chekuri and Rhea Jain. Approximation algorithms for network design in non-uniform fault models, 2024. arXiv:2403.15547, doi:10.48550/arXiv.2403.15547.
- [19] Vasek Chvátal. A greedy heuristic for the set-covering problem. Math. Oper. Res., 4(3):233–235, 1979. doi:10.1287/MOOR.4.3.233.
- [20] Efim A. Dinits, Alexander V. Karzanov, and Micael V. Lomonosov. On the structure of a family of minimum weighted cuts in a graph. Studies in Discrete Optimization, pages 209–306, 1976.
- [21] Gabriel L Duarte, Hiroshi Eto, Tesshu Hanaka, Yasuaki Kobayashi, Yusuke Kobayashi, Daniel Lokshtanov, Lehilton LC Pedrosa, Rafael CS Schouery, and Uéverton S Souza. Computing the largest bond and the maximum connected cut of a graph. Algorithmica, 83:1421–1458, 2021. doi:10.1007/S00453-020-00789-1.
- [22] Kapali P. Eswaran and Robert Endre Tarjan. Augmentation problems. SIAM J. Comput., 5(4):653–665, 1976. doi:10.1137/0205044.
- [23] Till Fluschnik, Stefan Kratsch, Rolf Niedermeier, and Manuel Sorge. The parameterized complexity of the minimum shared edges problem. J. Comput. Syst. Sci., 106:23–48, 2019. doi:10.1016/J.JCSS.2018.12.002.
- [24] Fedor V. Fomin, Petr A. Golovach, and Janne H. Korhonen. On the parameterized complexity of cutting a few vertices from a graph. In MFCS, volume 8087 of Lecture Notes in Computer Science, pages 421–432. Springer, 2013. doi:10.1007/978-3-642-40313-2_38.
- [25] Greg N. Frederickson and Joseph F. JáJá. Approximation algorithms for several graph augmentation problems. SIAM J. Comput., 10(2):270–283, 1981. doi:10.1137/0210019.
- [26] Harold N. Gabow. Data structures for weighted matching and nearest common ancestors with linking. In SODA, pages 434–443. SIAM, 1990. URL: http://dl.acm.org/citation.cfm?id=320176.320229.
- [27] M. R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979.
- [28] Naveen Garg, Vijay V. Vazirani, and Mihalis Yannakakis. Primal-dual approximation algorithms for integral flow and multicut in trees. Algorithmica, 18(1):3–20, 1997. doi:10.1007/BF02523685.
- [29] 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 SODA, pages 223–232. ACM/SIAM, 1994. URL: http://dl.acm.org/citation.cfm?id=314464.314497.
- [30] Zhongtian He, Shang-En Huang, and Thatchaphol Saranurak. Cactus representation of minimum cuts: Derandomize and speed up. In SODA, pages 1503–1541. SIAM, 2024. doi:10.1137/1.9781611977912.61.
- [31] Dorit S. Hochbaum. Approximation algorithms for the set covering and vertex cover problems. SIAM J. Comput., 11(3):555–556, 1982. doi:10.1137/0211045.
- [32] Kamal Jain. A factor 2 approximation algorithm for the generalized steiner network problem. Comb., 21(1):39–60, 2001. doi:10.1007/S004930170004.
- [33] David R. Karger. Global min-cuts in RNC, and other ramifications of a simple min-cut algorithm. In SODA, pages 21–30. ACM/SIAM, 1993. URL: http://dl.acm.org/citation.cfm?id=313559.313605.
- [34] Guy Kortsarz, Robert Krauthgamer, and James R. Lee. Hardness of approximation for vertex-connectivity network design problems. SIAM J. Comput., 33(3):704–720, 2004. doi:10.1137/S0097539702416736.
- [35] Hiroshi Nagamochi and Toshihide Ibaraki. Algorithmic Aspects of Graph Connectivity, volume 123 of Encyclopedia of Mathematics and its Applications. Cambridge University Press, 2008. doi:10.1017/CBO9780511721649.
- [36] Hiroshi Nagamochi, Kazuhiro Nishimura, and Toshihide Ibaraki. Computing all small cuts in an undirected network. SIAM J. Discret. Math., 10(3):469–481, 1997. doi:10.1137/S0895480194271323.
- [37] Zeev Nutov. Improved approximation ratio for covering pliable set families, 2024. arXiv:2404.00683, doi:10.48550/arXiv.2404.00683.
- [38] Masoud T. Omran, Jörg-Rüdiger Sack, and Hamid Zarrabi-Zadeh. Finding paths with minimum shared edges. J. Comb. Optim., 26(4):709–722, 2013. doi:10.1007/S10878-012-9462-2.
- [39] David Pritchard. k-edge-connectivity: Approximation and LP relaxation. In WAOA, volume 6534 of Lecture Notes in Computer Science, pages 225–236. Springer, 2010. doi:10.1007/978-3-642-18318-8_20.
- [40] Vera Traub and Rico Zenklusen. A better-than-2 approximation for weighted tree augmentation. In FOCS, pages 1–12. IEEE, 2021. doi:10.1109/FOCS52979.2021.00010.
- [41] Vera Traub and Rico Zenklusen. Local search for weighted tree augmentation and steiner tree. In SODA, pages 3253–3272. SIAM, 2022. doi:10.1137/1.9781611977073.128.
- [42] Vera Traub and Rico Zenklusen. A (1.5+)-approximation algorithm for weighted connectivity augmentation. In STOC, pages 1820–1833. ACM, 2023. doi:10.1145/3564246.3585122.
- [43] David P. Williamson, Michel X. Goemans, Milena Mihail, and Vijay V. Vazirani. A primal-dual approximation algorithm for generalized steiner network problems. Comb., 15(3):435–454, 1995. doi:10.1007/BF01299747.
- [44] Jianan Zhang, Eytan Modiano, and David Hay. Enhancing network robustness via shielding. IEEE/ACM Transactions on Networking, 25(4):2209–2222, 2017. doi:10.1109/TNET.2017.2689019.