# An Overview of Algorithms for Network Survivability

Authors: F. A. Kuipers
Journal: ISRN Communications and Networking
 (2012)

---

## Abstract

Network survivability—the ability to maintain operation when one or a few network components fail—is indispensable for present-day networks. In this paper, we characterize three main components in establishing network survivability for an existing network, namely, (1) determining network connectivity, (2) augmenting the network, and (3) finding disjoint paths. We present a concise overview of network survivability algorithms, where we focus on presenting a few polynomial-time algorithms that could be implemented by practitioners and give references to more involved algorithms.


---

## Body

## 1. Introduction

Given the present-day importance of communications systems and infrastructures in general, networks should be designed and operated in such a way that failures can be mitigated. Network nodes and/or links might for instance fail due to malicious attacks, natural disasters, unintentional cable cuts, planned maintenance, equipment malfunctioning, and so forth. Resilient, fault tolerant, survivable, reliable, robust, and dependable, are different terms that have been used by the networking community to capture the ability of a communications system to maintain operation when confronted with network failures. Unfortunately, the terminology has overlapping meanings or contains ambiguities, as pointed out by Al-Kuwaiti et al. [1]. In this paper, we will use the term survivable networks to refer to networks that, when a component fails, may “survive” by finding alternative paths that circumvent the failed component. Three ingredients are needed to reach survivability.(1)
Network connectivity, that is, the network should be well connected (connectivity properties are discussed in Section 1.1).(2)
Network augmentation, that is, new links may need to be added to increase the connectivity of a network.(3)
Path protection, that is, a procedure to find alternative paths in case of failures.These three ingredients will be explained in the following sections.


### 1.1. Network Connectivity

A network is often represented as a graphG(𝒩,ℒ), where 𝒩 is the set of N nodes (which for instance represent routers) and ℒ is the set of L links (which for instance represent optical fiber lines or radio channels). Links may be characterized by weights representing for instance their capacity, delay, length, cost, and/or failure probability. A graph is said to be connected if there exists a path between each pair of nodes in the graph, else the graph is said to be disconnected. In the context of survivability, the notion of connectivity may be further specified as k-connectivity, where at least k disjoint paths exist between each pair of nodes. Depending on whether these paths are node or link disjoint, we may discriminate between node and link connectivity. The link connectivity λ(G) of a graph G is the smallest number of links whose removal disconnects G. Correspondingly, the node connectivity κ(G) of a graph is the smallest number of nodes whose removal disconnects G.In 1927, Menger provided a theorem [2]—in German—that could be interpreted as follows.Theorem 1 (Menger's theorem).
The maximum number of link/node-disjoint paths between A and B is equal to the minimum number of links/nodes that would separate A and B.Menger's theorem clearly relates to thek link/node connectivity of a graph, in the sense that a k link/node-connected graph has at least k link/node-disjoint paths between any pair of nodes in the graph. The minimum number of links/nodes separating two nodes or sets of nodes is referred to as a minimum cut. In order to assess the link/node connectivity of a network, we therefore need to find its minimum cut.A somewhat less intuitive notion of connectivity stems from the spectrum of the Laplacian matrix of a graph and is denoted as algebraic connectivity. The algebraic connectivity was introduced by Fiedler in 1973 [3] and is defined as follows.Definition 2 (algebraic connectivity).
The algebraic connectivity equals the value of the second smallest eigenvalue ofQ, where Q is the Laplacian matrix Q=Δ-A, with A an N×N adjacency matrix with elements aij=1 if there is a link between nodes i and j, else aij=0, and Δ=diag(d1,…,dN) an N×N diagonal matrix with dj the degree of node j.The algebraic connectivity has many interesting properties that characterize how strongly a graphG is connected (e.g., see [4, 5]). Moreover, the multiplicity of the smallest eigenvalue (of value 0) of the Laplacian Q is equal to the number of components in the graph G. Hence, if the algebraic connectivity α(G) is larger than 0, the network is connected, else the algebraic connectivity is 0, and the network is disconnected. We have that
(1)α(G)≤κ(G)≤λ(G)≤δ(G),
where δ(G) is the minimum degree in the network. For ease of notation, when G is not specified, we use α, κ, λ, and δ.Connectivity properties, may be less obvious when applied to multilayered networks [6, 7], like IP over WDM networks, where a 2-link-connected IP network operated on top of an optical WDM network, with multiple IP links sharing (e.g., groomed on) the same WDM link, could still be disconnected by a single-link failure at the optical layer.In probabilistic networks, links and/or nodesx are available with a certain probability px, which is often computed as px=MTTF(x)/(MTTF(x)+MTTR(x)), with MTTF(x) the mean time to failure of x and MTTR(x) the mean repair time of x. Often the term network availability is used to denote the probability that the network is connected (e.g., see [8]). When the node probabilities are all one and all the link probabilities are independent and of equal value p, then a reliability polynomial (a special case of the Tutte polynomial, e.g., see [9]) is a polynomial function in p that gives the probability that the network remains connected after its links fail with probability p.


### 1.2. Network Augmentation

The outcome of testing for network connectivity could be that the network is not sufficiently robust (connected). Possibly, rewiring the (overlay) network could improve its robustness properties [10]. However, this is more involved when applied to the physical network, and improving network performance or network robustness is therefore often established by adding new links and possibly also nodes to the network. Adding links or nodes can be costly (which could be reflected by link/node weights), and the new links/nodes should therefore be placed wisely, such that the desired network property is obtained with the fewest amount of links/nodes or such that the addition of a fixed amount of links/nodes maximizes the desired network property. This class of problems is referred to as (network) augmentation problems, and within this class the problems only differ in their objectives. For instance, k-connectivity is an important property in the context of network robustness, and reaching it through link additions might be one such objective. The alternative objective of algebraic connectivity augmentation leads to an NP-hard problem [11]. Similarly, adding a minimum amount of links to make a graph chordal  is also NP-hard [12] (a graph is chordal if each of its cycles of four or more nodes has a link connecting two nonadjacent nodes in the cycle).


### 1.3. Path Protection

Network protocols like OSPF are deployed in the internet to obtain a correct view of the topology and in case of changes (like the failure of a link) to converge the routing towards the new (perturbed) situation. Unfortunately, this process is not fast, and applications may still face unacceptable disruptions in performance. In conjunction with MPLS, an MPLS fast reroute mechanism can be used that, as the name suggests, provides the ability to switch over in subsecond time from a failed primary path to an alternate (backup) path. This fast reroute mechanism is specified in RFC 4090 [13], May 2005, and has already been implemented by several vendors. The concept has also been extended to pure IP networks and is referred to as IP fast reroute [14]. RFC 4090 defines RSVP-TE extensions to establish backup label-switched path (LSP) tunnels for local repair of LSP tunnels. The backup path can either be configured to protect against a link or a node failure. Since the backup paths are precomputed, no time is lost in computing backup paths or performing signalling in the event of a failure. The fast reroute mechanism as described in RFC 4090 assumes that MPLS (primary and backup) paths are computed and explicitly routed by the network operator. Hence, there is a strong need for efficient algorithms to compute disjoint paths.Depending on whether backup paths are computed before or after a failure of the primary path, survivability techniques can be broadly classified into restoration or protection techniques.(i)
Protection scheme: protection is a proactive scheme, where backup paths are precomputed and reserved in advance. In 1 : 1 protection, traffic is rerouted along the backup path upon the failure of the primary path. In 1+1 protection, the data is duplicated and sent concurrently over the primary and backup paths.(ii)
Restoration scheme: restoration is a reactive mechanism that handles a failure after it occurs. Thus, the backup path is not known a priori. Instead, a backup path is computed only after the failure in the primary path is sensed.In general, protection has a shorter recovery time since the backup path is precomputed, but it is less efficient in terms of capacity utilization and less flexible. Restoration, on the other hand, provides increased flexibility and efficient resource utilization, but it may take a longer time for recovery, and there is no guarantee that a backup path will be found. As a compromise between the two schemes, Banner and Orda [15] considered designing a low-capacity backup network (using spare capacity or by installing new resources) that is fully provisioned to reroute traffic on the primary network in case of a failure. The backup network itself is not used to transport “primary” traffic. Backup networks with specific topological features have also been addressed in the literature, for instance protection [16] and preconfigured [17] cycles or redundant trees [18].Depending on how rerouting is done after a failure in the primary path, there are three categories of survivability techniques.(i)
Path-based protection/restoration: in path-based protection, a link- or node-disjoint backup path is precomputed and takes over when the primary path fails. In path-based restoration, a new path is computed between the source and destination nodes of the failed path. If such a backup path cannot be found, the request is blocked.(ii)
Link-based protection/restoration: in link-based protection, each link is preassigned a local route that is used when the link fails, and in link-based restoration, the objective is to compute a detour between the two ends of the failed link for all paths that are using the link. Since link-based protection/restoration requires signaling only between the two ends of the failed link, it has a smaller recovery time than path-based protection/restoration, which requires end-to-end signaling between the source and destination nodes.(iii)
Segment-based protection/restoration: the segment-based scheme (e.g., see [19]) is a compromise between path-based and link-based schemes. Thus, in segment-based protection, backup routes are precomputed for segments of the primary path. In segment-based restoration, a detour of the segment containing the failed link is computed following a failure.Depending on whether sharing of resources is allowed among backup paths, protection schemes can be of two types:(i)
Dedicated protection: in this scheme, resources (e.g., links, wavelength channels, etc.) are not shared among backup paths and are exclusively reserved for a given path request.(ii)
Shared protection: in this scheme, backup paths may share resources as long as their primary paths do not share links. In M : N protection, M backup paths are used to protect N primary paths. The shared scheme provides a better resource utilization; however, it is more complicated and requires more information, such as the shareability of each link.In general, path protection requires less capacity than link protection, while shared protection requires less capacity than dedicated protection. However, path protection is more vulnerable to multiple link failures than link protection, and so is shared protection compared to dedicated protection.


### 1.4. Paper Outline and Objective

The remainder of this paper is structured as follows. In Section2, we give an overview of several methods for determining the connectivity properties of a network. In case a network is found to be insufficiently connected from a survivability perspective, links may have to be added to increase the connectivity. In Section 3, we list key results in network connectivity augmentation. Once a network is designed to withstand some failures, proper path protection/restoration schemes should be in place that can quickly defer traffic to alternate routes in case of a failure. In Section 4, we survey work on finding disjoint paths in a network. We conclude in Section 5.Throughout the paper, the objective is not to list and explain all the relevant algorithms. Rather, we aim to briefly explain some fundamental concepts and some polynomial-time algorithms that could easily be deployed by practitioners or which can be (and have been) used as building blocks for more advanced algorithms, and to provide pointers to further reading.


## 1.1. Network Connectivity

A network is often represented as a graphG(𝒩,ℒ), where 𝒩 is the set of N nodes (which for instance represent routers) and ℒ is the set of L links (which for instance represent optical fiber lines or radio channels). Links may be characterized by weights representing for instance their capacity, delay, length, cost, and/or failure probability. A graph is said to be connected if there exists a path between each pair of nodes in the graph, else the graph is said to be disconnected. In the context of survivability, the notion of connectivity may be further specified as k-connectivity, where at least k disjoint paths exist between each pair of nodes. Depending on whether these paths are node or link disjoint, we may discriminate between node and link connectivity. The link connectivity λ(G) of a graph G is the smallest number of links whose removal disconnects G. Correspondingly, the node connectivity κ(G) of a graph is the smallest number of nodes whose removal disconnects G.In 1927, Menger provided a theorem [2]—in German—that could be interpreted as follows.Theorem 1 (Menger's theorem).
The maximum number of link/node-disjoint paths between A and B is equal to the minimum number of links/nodes that would separate A and B.Menger's theorem clearly relates to thek link/node connectivity of a graph, in the sense that a k link/node-connected graph has at least k link/node-disjoint paths between any pair of nodes in the graph. The minimum number of links/nodes separating two nodes or sets of nodes is referred to as a minimum cut. In order to assess the link/node connectivity of a network, we therefore need to find its minimum cut.A somewhat less intuitive notion of connectivity stems from the spectrum of the Laplacian matrix of a graph and is denoted as algebraic connectivity. The algebraic connectivity was introduced by Fiedler in 1973 [3] and is defined as follows.Definition 2 (algebraic connectivity).
The algebraic connectivity equals the value of the second smallest eigenvalue ofQ, where Q is the Laplacian matrix Q=Δ-A, with A an N×N adjacency matrix with elements aij=1 if there is a link between nodes i and j, else aij=0, and Δ=diag(d1,…,dN) an N×N diagonal matrix with dj the degree of node j.The algebraic connectivity has many interesting properties that characterize how strongly a graphG is connected (e.g., see [4, 5]). Moreover, the multiplicity of the smallest eigenvalue (of value 0) of the Laplacian Q is equal to the number of components in the graph G. Hence, if the algebraic connectivity α(G) is larger than 0, the network is connected, else the algebraic connectivity is 0, and the network is disconnected. We have that
(1)α(G)≤κ(G)≤λ(G)≤δ(G),
where δ(G) is the minimum degree in the network. For ease of notation, when G is not specified, we use α, κ, λ, and δ.Connectivity properties, may be less obvious when applied to multilayered networks [6, 7], like IP over WDM networks, where a 2-link-connected IP network operated on top of an optical WDM network, with multiple IP links sharing (e.g., groomed on) the same WDM link, could still be disconnected by a single-link failure at the optical layer.In probabilistic networks, links and/or nodesx are available with a certain probability px, which is often computed as px=MTTF(x)/(MTTF(x)+MTTR(x)), with MTTF(x) the mean time to failure of x and MTTR(x) the mean repair time of x. Often the term network availability is used to denote the probability that the network is connected (e.g., see [8]). When the node probabilities are all one and all the link probabilities are independent and of equal value p, then a reliability polynomial (a special case of the Tutte polynomial, e.g., see [9]) is a polynomial function in p that gives the probability that the network remains connected after its links fail with probability p.


## 1.2. Network Augmentation

The outcome of testing for network connectivity could be that the network is not sufficiently robust (connected). Possibly, rewiring the (overlay) network could improve its robustness properties [10]. However, this is more involved when applied to the physical network, and improving network performance or network robustness is therefore often established by adding new links and possibly also nodes to the network. Adding links or nodes can be costly (which could be reflected by link/node weights), and the new links/nodes should therefore be placed wisely, such that the desired network property is obtained with the fewest amount of links/nodes or such that the addition of a fixed amount of links/nodes maximizes the desired network property. This class of problems is referred to as (network) augmentation problems, and within this class the problems only differ in their objectives. For instance, k-connectivity is an important property in the context of network robustness, and reaching it through link additions might be one such objective. The alternative objective of algebraic connectivity augmentation leads to an NP-hard problem [11]. Similarly, adding a minimum amount of links to make a graph chordal  is also NP-hard [12] (a graph is chordal if each of its cycles of four or more nodes has a link connecting two nonadjacent nodes in the cycle).


## 1.3. Path Protection

Network protocols like OSPF are deployed in the internet to obtain a correct view of the topology and in case of changes (like the failure of a link) to converge the routing towards the new (perturbed) situation. Unfortunately, this process is not fast, and applications may still face unacceptable disruptions in performance. In conjunction with MPLS, an MPLS fast reroute mechanism can be used that, as the name suggests, provides the ability to switch over in subsecond time from a failed primary path to an alternate (backup) path. This fast reroute mechanism is specified in RFC 4090 [13], May 2005, and has already been implemented by several vendors. The concept has also been extended to pure IP networks and is referred to as IP fast reroute [14]. RFC 4090 defines RSVP-TE extensions to establish backup label-switched path (LSP) tunnels for local repair of LSP tunnels. The backup path can either be configured to protect against a link or a node failure. Since the backup paths are precomputed, no time is lost in computing backup paths or performing signalling in the event of a failure. The fast reroute mechanism as described in RFC 4090 assumes that MPLS (primary and backup) paths are computed and explicitly routed by the network operator. Hence, there is a strong need for efficient algorithms to compute disjoint paths.Depending on whether backup paths are computed before or after a failure of the primary path, survivability techniques can be broadly classified into restoration or protection techniques.(i)
Protection scheme: protection is a proactive scheme, where backup paths are precomputed and reserved in advance. In 1 : 1 protection, traffic is rerouted along the backup path upon the failure of the primary path. In 1+1 protection, the data is duplicated and sent concurrently over the primary and backup paths.(ii)
Restoration scheme: restoration is a reactive mechanism that handles a failure after it occurs. Thus, the backup path is not known a priori. Instead, a backup path is computed only after the failure in the primary path is sensed.In general, protection has a shorter recovery time since the backup path is precomputed, but it is less efficient in terms of capacity utilization and less flexible. Restoration, on the other hand, provides increased flexibility and efficient resource utilization, but it may take a longer time for recovery, and there is no guarantee that a backup path will be found. As a compromise between the two schemes, Banner and Orda [15] considered designing a low-capacity backup network (using spare capacity or by installing new resources) that is fully provisioned to reroute traffic on the primary network in case of a failure. The backup network itself is not used to transport “primary” traffic. Backup networks with specific topological features have also been addressed in the literature, for instance protection [16] and preconfigured [17] cycles or redundant trees [18].Depending on how rerouting is done after a failure in the primary path, there are three categories of survivability techniques.(i)
Path-based protection/restoration: in path-based protection, a link- or node-disjoint backup path is precomputed and takes over when the primary path fails. In path-based restoration, a new path is computed between the source and destination nodes of the failed path. If such a backup path cannot be found, the request is blocked.(ii)
Link-based protection/restoration: in link-based protection, each link is preassigned a local route that is used when the link fails, and in link-based restoration, the objective is to compute a detour between the two ends of the failed link for all paths that are using the link. Since link-based protection/restoration requires signaling only between the two ends of the failed link, it has a smaller recovery time than path-based protection/restoration, which requires end-to-end signaling between the source and destination nodes.(iii)
Segment-based protection/restoration: the segment-based scheme (e.g., see [19]) is a compromise between path-based and link-based schemes. Thus, in segment-based protection, backup routes are precomputed for segments of the primary path. In segment-based restoration, a detour of the segment containing the failed link is computed following a failure.Depending on whether sharing of resources is allowed among backup paths, protection schemes can be of two types:(i)
Dedicated protection: in this scheme, resources (e.g., links, wavelength channels, etc.) are not shared among backup paths and are exclusively reserved for a given path request.(ii)
Shared protection: in this scheme, backup paths may share resources as long as their primary paths do not share links. In M : N protection, M backup paths are used to protect N primary paths. The shared scheme provides a better resource utilization; however, it is more complicated and requires more information, such as the shareability of each link.In general, path protection requires less capacity than link protection, while shared protection requires less capacity than dedicated protection. However, path protection is more vulnerable to multiple link failures than link protection, and so is shared protection compared to dedicated protection.


## 1.4. Paper Outline and Objective

The remainder of this paper is structured as follows. In Section2, we give an overview of several methods for determining the connectivity properties of a network. In case a network is found to be insufficiently connected from a survivability perspective, links may have to be added to increase the connectivity. In Section 3, we list key results in network connectivity augmentation. Once a network is designed to withstand some failures, proper path protection/restoration schemes should be in place that can quickly defer traffic to alternate routes in case of a failure. In Section 4, we survey work on finding disjoint paths in a network. We conclude in Section 5.Throughout the paper, the objective is not to list and explain all the relevant algorithms. Rather, we aim to briefly explain some fundamental concepts and some polynomial-time algorithms that could easily be deployed by practitioners or which can be (and have been) used as building blocks for more advanced algorithms, and to provide pointers to further reading.


## 2. Determining Network Connectivity

In Section1.1, we indicated that Menger's theorem implies that finding a minimum cut corresponds to finding the connectivity of a network. In this section, we will look further at finding cuts in a network.Definition 3 (link (edge) cut).
A link cut refers to a set of links whose removal separates the graph into two disjoint subgraphs, and where all links in the removed cut-set have an end-point in both subgraphs.The two subgraphs need not be connected themselves.Definition 4 (node (vertex) cut).
A node cut refers to a set of nodes whose removal separates the graph into two disjoint subgraphs, and where all nodes in the removed cut-set have at least one adjacent link to both subgraphs.Definition 5 (minimum link/node cut).
A minimum cut is a cut whose cardinality is not larger than that of any other cut in the network.Definitions for a cut also have a variant in which a source nodes and a terminating node t need to be separated.Definition 6 (s-t cut).
Ans-t cut refers to a cut that separates two nodes s and t in the graph such that both belong to different subgraphs.Often, when referring to a cut, a link cut is meant. In the remainder of this paper, we will use the same convention and only specify the type of cut for node cuts.Definition 7 (maximum cut).
A maximum cut is a cut whose cardinality is not exceeded by that of any other cut in the network.Definition 8 (sparsest cut).
The sparsest cut (sometimes also referred to as the (Cheeger)  isoperimetric constant)  is a cut for which the ratio of the number of links in the cut-set divided by the number of nodes in the smaller subgraph is not larger than that of any other cut in the network.Finding a maximum or sparsest cut is a hard problem (the maximum-cut problem is APX-hard [20] and the sparsest-cut problem is NP-hard [21, 22]), but fortunately a minimum cut, and consequently the network's connectivity, can be computed in polynomial time as will be indicated below. The algebraic connectivity α could be used to approximate the sparsest cut γ as α/2≤γ≤α(2δ-α)  [4, 21]. Dinh et al. [23]  investigated the notion of pairwise connectivity (the number of connected pairs, which bears similarities to the sparsest-cut problem), and proved that finding the smallest set of nodes/links whose removal degrades the pairwise connectivity to certain degree is NP-complete.


### 2.1. Determining Link Connectivity

In the celebrated paper from Ford and Fulkerson [24] (and independently by Elias et al. [25]) a maximum flow from a source s to a terminal t in a network, where the links have a given capacity, is shown to be equal to the minimum-weight s-t link cut in that network, where the weight of the cut is the sum of the capacities of the links in the cut-set; the so-called max-flow min-cut theorem. By using a max-flow algorithm and setting the capacity of all links to 1, one can therefore compute the minimum s-t link cut, or the minimum link cut when repeated over all possible s-t pairs. It is not our goal to overview all maximum-flow algorithms (an excellent discourse of the subject is presented in the book by Ahuja et al. [26]), but we will present Dinitz's algorithm, which can be used to determine the minimum s-t link cut in O(L·(min{N2/3,L})) time. We will subsequently present the algorithm of Matula for determining the minimum link cut in O(NL) time.


#### 2.1.1. Dinitz' Algorithm

Dinitz' algorithm, published in 1970 by Yefim Dinitz, was the first maximum-flow algorithm to run in polynomial time (contrary to the pseudopolynomial running time of the Ford-Fulkerson algorithm [24]). The algorithm is sometimes referred to as Dinic's or Dinits' algorithm, and also different variants are known. A historical perspective of the different variants is presented by Dinitz himself in [27]. In order to describe Dinitz' algorithm, as presented in Algorithm 1, some definitions are given.Algorithm 1:Dinitz-Max-Flow (G,c,s,t).
(
1
)  f(u,v)←0∀(u,v)∈ℒ and f*←0 /*Initialize to zero flow*/
(2) While /*loop until the algorithm terminates in line9*/
(3)For all nodes u∈𝒩, compute in Gf the hopcount h(u) to t /*by
Breadth-First-Search [28] from t*/
(4)Compute a blocking flow f in Gf thereby skipping links (u,v) for which
h(v)≠h(u)+1
(5)If f exists
(6)f*←f*+f
(7)Update Gf
(8)else
(9) return f*Definition 9.
The residual capacitycf(u,v) of a link (u,v) is interpreted in two directions as follows:
(2)cf(u,v)=c(u,v)-f(u,v),cf(v,u)=f(u,v),
where the flow f(u,v) over a link (u,v) cannot exceed the capacity c(u,v) of that link.Definition 10.
The residual graphGf of G is the graph in which a directed link (u,v) exists if cf(u,v)>0.Definition 11.
A blocking flowfb is an s-t flow such that any other s-t flow f would have to traverse a link already saturated by fb.A blocking flow could be obtained by repeatedly finding (via Depth-First-Search [28]) an  augmenting flow along an s-t path (or pruning the path from the graph in unit-capacity networks). In unit-capacity networks, the algorithm runs in O(L·(min{N2/3,L})), which therefore also is the time complexity to determine a minimum s-t link cut with Dinitz' algorithm (for unit node capacities, a complexity of O(LN) can be obtained [29]).For further reference, in Table1, we present some key achievements in computing minimum s-t link cuts.Table 1
Related work on computing minimums-t link cuts.
Year1
Reference
Complexity
Description
1951
Dantzig [30]
O
(
N
2
L
U
)
Linear programming, whereU is the largest link capacity.
1956
Ford and Fulkerson [31]
O
(
N
L
U
)
Augmenting paths.
1970
Dinitz [27]
O
(
N
2
L
), O(L·(min{N2/3,L}))
Resp. capacitated and unit-capacity graphs. Shortest augmenting paths.
1974
Karzanov [32]
O
(
N
3
)
Preflow-push (A simplification of Karzanov's algorithm has been presented by Tarjan [33]).
1980
Galil and Naamad [34]
O
(
N
L
log
2
N
)
Extension of Dinitz' algorithm.
1982
Shiloach and Vishkin [35]
O
(
(
N
3
log
N
)
/
p
)
Parallel algorithm forp≤N processors.
1983
Sleator and  Tarjan  [36]
O
(
N
L
log
N
)
Dynamic tree data structure.
1986
Goldberg and Tarjan [37]
O
(
N
L
log
(
N
2
/
L
)
)
Highest-label preflow-push.
1987
Ahuja et al. [38]
O
(
N
L
log
(
(
N
/
L
)
log
U
+
2
)
)
Excess scaling.
1989
Cheriyan and Hagerup [39]
O
(
N
L
+
N
2
log
3
N
)
Randomized algorithm.
1990
Alon [40]
O
(
N
L
)
Deterministic version of Cheriyan and Hagerup's randomized algorithm.
1998
Goldberg and Rao [41]
O
(
min
{
N
2
/
3
,
L
}
L
log
(
N
2
/
L
)
log
U
)
Length function.
2011
Christiano et al. [42]
O
~
(
L
N
1
/
3
ϵ
-
11
/
3
), O~(L+N4/3ϵ-8/3)
Resp.(1-ϵ) and (1+ϵ) approximation, where O~(f(x)) denotes O(f(x)logcf(x)) for some constant c.
1Throughout the paper, we take the convention of listing the year of the first (conference) publication, while referring to the extended (journal) version there where applicable.


#### 2.1.2. Matula's Algorithm

In this section, we describe the algorithm from Matula [43] for determining the link connectivity of an undirected network. Matula's algorithm is based on the following lemma.Lemma 12.
LetG be a graph with a minimum cut of size λ(G)≤δ(G)-1 that partitions the graph G into two subgraphs G1(𝒩1,ℒ1) and G2(𝒩2,ℒ2), then any dominating set S of G contains nodes of both G1 and G2  (a dominating set S∈𝒩 is a subset of the nodes in G, such that every node in 𝒩 is either in S or adjacent to a node in S).Proof.
For subgraphGi, i=1,2, holds that the sum of the nodal degrees in Gi is bounded by
(3)Ni(Ni-1)+λ(G)≥∑u∈Gid(u)≥Niδ(G).
The upper bound occurs if all nodes in Gi are connected to each other and some of the nodes have a link that is part of the cut-set. The lower bound stems from each node having a degree larger or equal than the minimum degree δ(G). From the bounds in (3), we can derive that
(4)(Ni-δ(G))(Ni-1)≥δ(G)-λ(G).
Since λ(G)≤δ(G)-1 is assumed, (Ni-δ(G))(Ni-1)≥1 and consequently both terms on the left-hand side cannot be smaller than 1. Hence, Ni-δ(G)≥1, which means that, under the assumption that λ(G)≤δ(G)-1, there is at least one node in G1 that does not have a neighbor in G2 (and vice versa). In other words, any dominating set S of G should contain nodes of both G1 and G2.The algorithm of Matula (see Algorithm2) starts with a node of minimum degree (e.g., node s in G1) and gradually builds a dominating set S by adding nodes not yet part of or adjacent to the growing set. Since at one point a node, for example u*, from G2 needs to be added, keeping track of the minimum cut between newly added dominating nodes, and S will result in finding the overall minimum cut. The algorithm is presented below.Algorithm 2:Matula-Min-Cut (G).
(
1
) For a node s of minimum degree set S←{s}, T←{t∣t∈adj(s)}, U←𝒩-S-T, and λ←d(s).
(2) WhileU≠∅
(3) Choose u∈U
(4) n← The number of shortest augmenting paths from u to S
(5) If n<λ then λ←n
(6) Set S←S∪u, T←T∪{t∣t∈adj(u)}, followed by U←𝒩-S-TIn the algorithm of Matula, an augmenting path is a path in the residual network, where a residual network is the network that remains after pruning the links of a previous augmenting path. There are no 1-hop paths fromu* to S, because then u*∈T. If u* has nT neighbors that belong to T, then there exist nT 2-hop paths from u* to S, for which either the first hop from u* to T or the second hop from T to S is part of the minimum cut. These nT paths form the first augmenting paths, after which λ(G)-nT remains. These remaining augmenting paths can be found in O(L) time each and since there are at most d(u*)-nT such paths, the complexity of the algorithm is bounded by O(NL). Finally, if λ(G)=δ(G), then the initialization guarantees that that value would be found.For directed multigraphs, Shiloach [44] provided a theorem that is stronger than Menger's theorem, namely.Theorem 13.
LetG be a directed k-link-connected multigraph, then for all s1,…,sk, t1,…,tk∈𝒩 (not necessarily distinct) there exist link-disjoint paths Pi from si to ti for i=1,…,k.We refer to Mansour and Schieber [45] for an O(NL)-time algorithm for determining the link connectivity in directed networks.For further reference, in Table2 we present some key achievements in computing minimum link cuts.Table 2
Related work on computing minimum link cuts.
Year
Reference
Complexity
Description
1971
Podderyugin[70]
O
(
N
L
)
Undirected graphs. Variation of Ford-Fulkerson max-flow algorithm in how augmenting paths of one and two hops are handled.
1971
Tarjan [67]
O
(
N
+
L
)
Testing for 2-link connectivity in undirected graphs via DFS.
1975
Even and Tarjan [29]
O
(
N
5
/
3
L
)
Application of Dinitz' algorithm.
1986
Karzanov and Timofeev [59]
O
(
λ
N
2
)
Undirected graphs.
1987
Matula [43]
O
(
N
L
), O(λN2)
Undirected graphs. It is also shown that the maximum subgraph link connectivity can be determined inO(N2L).
1989
Mansour and Schieber [45]
O
(
N
L
), O(λ2N2)
Directed graphs. Relation between minimum cut and dominating set.
1990
Nagamochi and Ibaraki [71]
O
(
L
+
λ
N
2
)
Undirected graphs. Algorithm does not use a max-flow algorithm.
1991
Galil and Italiano [72]
O
(
N
+
L
)
Testing for 3-link-connectivity in undirected graphs.
1991
Gabow [73]
O
(
λ
L
log
(
N
2
/
L
)
), O(L+λ2Nlog(N/λ))
Directed, resp. undirected graphs. Matroid approach.
1996
Karger [74]
O
(
L
log
2
N
)
Randomized algorithm.


### 2.2. Determining Node Connectivity

Maximum-flow algorithms can also be used to determine the node connectivity, as demonstrated by Dantzig and Fulkerson [46] (and also discussed in [47]), by transforming the undirected graph G(𝒩,ℒ) to a directed graph G′(𝒩′,ℒ′) as follows.For every noden∈𝒩 place two nodes n′ and n′′ in 𝒩′ and connect them via a directed link (n′,n′′), using the convention that the link starts at n′ and ends at n′′. For every undirected link (i,j)∈ℒ place directed links (i′′,j′) and (j′′,i′) in G′. All links are assigned unit capacity.Thes-t node connectivity in G can be computed by finding a maximum flow from s′′ to t′ in G′. This can be seen as follows. Assume that there are κ node-disjoint paths between s and t, then there are also κ corresponding node-disjoint paths from s′′ to t′ in G′. Since each link has unit capacity, there thus exists a flow of at least κ. Since each link entering a node n′∈G′ has to traverse a single unit-capacity link (n′,n′′) at most one unit of flow can pass through a node, which corresponds to a node-disjoint path. Since there are only κ node-disjoint paths, the maximum flow in G′ is equal to κ.By using Dinitz' algorithm, one may compute thes-t node connectivity in O(L·(min{N2/3,L})) time, and by using the algorithm of Mansour and Schieber [45], the node connectivity can be determined in O(NL) time. We refer to Henzinger et al. [48] and Gabow [49] for more advanced algorithms to compute the node connectivity in directed and undirected graphs and to Yoshida and Ito [50] for a κ-node-connectivity property testing  algorithm (in property testing the objective is to decide, with high probability, whether the input graph is close to having a certain property. These algorithms typically run in sub-linear time).


## 2.1. Determining Link Connectivity

In the celebrated paper from Ford and Fulkerson [24] (and independently by Elias et al. [25]) a maximum flow from a source s to a terminal t in a network, where the links have a given capacity, is shown to be equal to the minimum-weight s-t link cut in that network, where the weight of the cut is the sum of the capacities of the links in the cut-set; the so-called max-flow min-cut theorem. By using a max-flow algorithm and setting the capacity of all links to 1, one can therefore compute the minimum s-t link cut, or the minimum link cut when repeated over all possible s-t pairs. It is not our goal to overview all maximum-flow algorithms (an excellent discourse of the subject is presented in the book by Ahuja et al. [26]), but we will present Dinitz's algorithm, which can be used to determine the minimum s-t link cut in O(L·(min{N2/3,L})) time. We will subsequently present the algorithm of Matula for determining the minimum link cut in O(NL) time.


### 2.1.1. Dinitz' Algorithm

Dinitz' algorithm, published in 1970 by Yefim Dinitz, was the first maximum-flow algorithm to run in polynomial time (contrary to the pseudopolynomial running time of the Ford-Fulkerson algorithm [24]). The algorithm is sometimes referred to as Dinic's or Dinits' algorithm, and also different variants are known. A historical perspective of the different variants is presented by Dinitz himself in [27]. In order to describe Dinitz' algorithm, as presented in Algorithm 1, some definitions are given.Algorithm 1:Dinitz-Max-Flow (G,c,s,t).
(
1
)  f(u,v)←0∀(u,v)∈ℒ and f*←0 /*Initialize to zero flow*/
(2) While /*loop until the algorithm terminates in line9*/
(3)For all nodes u∈𝒩, compute in Gf the hopcount h(u) to t /*by
Breadth-First-Search [28] from t*/
(4)Compute a blocking flow f in Gf thereby skipping links (u,v) for which
h(v)≠h(u)+1
(5)If f exists
(6)f*←f*+f
(7)Update Gf
(8)else
(9) return f*Definition 9.
The residual capacitycf(u,v) of a link (u,v) is interpreted in two directions as follows:
(2)cf(u,v)=c(u,v)-f(u,v),cf(v,u)=f(u,v),
where the flow f(u,v) over a link (u,v) cannot exceed the capacity c(u,v) of that link.Definition 10.
The residual graphGf of G is the graph in which a directed link (u,v) exists if cf(u,v)>0.Definition 11.
A blocking flowfb is an s-t flow such that any other s-t flow f would have to traverse a link already saturated by fb.A blocking flow could be obtained by repeatedly finding (via Depth-First-Search [28]) an  augmenting flow along an s-t path (or pruning the path from the graph in unit-capacity networks). In unit-capacity networks, the algorithm runs in O(L·(min{N2/3,L})), which therefore also is the time complexity to determine a minimum s-t link cut with Dinitz' algorithm (for unit node capacities, a complexity of O(LN) can be obtained [29]).For further reference, in Table1, we present some key achievements in computing minimum s-t link cuts.Table 1
Related work on computing minimums-t link cuts.
Year1
Reference
Complexity
Description
1951
Dantzig [30]
O
(
N
2
L
U
)
Linear programming, whereU is the largest link capacity.
1956
Ford and Fulkerson [31]
O
(
N
L
U
)
Augmenting paths.
1970
Dinitz [27]
O
(
N
2
L
), O(L·(min{N2/3,L}))
Resp. capacitated and unit-capacity graphs. Shortest augmenting paths.
1974
Karzanov [32]
O
(
N
3
)
Preflow-push (A simplification of Karzanov's algorithm has been presented by Tarjan [33]).
1980
Galil and Naamad [34]
O
(
N
L
log
2
N
)
Extension of Dinitz' algorithm.
1982
Shiloach and Vishkin [35]
O
(
(
N
3
log
N
)
/
p
)
Parallel algorithm forp≤N processors.
1983
Sleator and  Tarjan  [36]
O
(
N
L
log
N
)
Dynamic tree data structure.
1986
Goldberg and Tarjan [37]
O
(
N
L
log
(
N
2
/
L
)
)
Highest-label preflow-push.
1987
Ahuja et al. [38]
O
(
N
L
log
(
(
N
/
L
)
log
U
+
2
)
)
Excess scaling.
1989
Cheriyan and Hagerup [39]
O
(
N
L
+
N
2
log
3
N
)
Randomized algorithm.
1990
Alon [40]
O
(
N
L
)
Deterministic version of Cheriyan and Hagerup's randomized algorithm.
1998
Goldberg and Rao [41]
O
(
min
{
N
2
/
3
,
L
}
L
log
(
N
2
/
L
)
log
U
)
Length function.
2011
Christiano et al. [42]
O
~
(
L
N
1
/
3
ϵ
-
11
/
3
), O~(L+N4/3ϵ-8/3)
Resp.(1-ϵ) and (1+ϵ) approximation, where O~(f(x)) denotes O(f(x)logcf(x)) for some constant c.
1Throughout the paper, we take the convention of listing the year of the first (conference) publication, while referring to the extended (journal) version there where applicable.


### 2.1.2. Matula's Algorithm

In this section, we describe the algorithm from Matula [43] for determining the link connectivity of an undirected network. Matula's algorithm is based on the following lemma.Lemma 12.
LetG be a graph with a minimum cut of size λ(G)≤δ(G)-1 that partitions the graph G into two subgraphs G1(𝒩1,ℒ1) and G2(𝒩2,ℒ2), then any dominating set S of G contains nodes of both G1 and G2  (a dominating set S∈𝒩 is a subset of the nodes in G, such that every node in 𝒩 is either in S or adjacent to a node in S).Proof.
For subgraphGi, i=1,2, holds that the sum of the nodal degrees in Gi is bounded by
(3)Ni(Ni-1)+λ(G)≥∑u∈Gid(u)≥Niδ(G).
The upper bound occurs if all nodes in Gi are connected to each other and some of the nodes have a link that is part of the cut-set. The lower bound stems from each node having a degree larger or equal than the minimum degree δ(G). From the bounds in (3), we can derive that
(4)(Ni-δ(G))(Ni-1)≥δ(G)-λ(G).
Since λ(G)≤δ(G)-1 is assumed, (Ni-δ(G))(Ni-1)≥1 and consequently both terms on the left-hand side cannot be smaller than 1. Hence, Ni-δ(G)≥1, which means that, under the assumption that λ(G)≤δ(G)-1, there is at least one node in G1 that does not have a neighbor in G2 (and vice versa). In other words, any dominating set S of G should contain nodes of both G1 and G2.The algorithm of Matula (see Algorithm2) starts with a node of minimum degree (e.g., node s in G1) and gradually builds a dominating set S by adding nodes not yet part of or adjacent to the growing set. Since at one point a node, for example u*, from G2 needs to be added, keeping track of the minimum cut between newly added dominating nodes, and S will result in finding the overall minimum cut. The algorithm is presented below.Algorithm 2:Matula-Min-Cut (G).
(
1
) For a node s of minimum degree set S←{s}, T←{t∣t∈adj(s)}, U←𝒩-S-T, and λ←d(s).
(2) WhileU≠∅
(3) Choose u∈U
(4) n← The number of shortest augmenting paths from u to S
(5) If n<λ then λ←n
(6) Set S←S∪u, T←T∪{t∣t∈adj(u)}, followed by U←𝒩-S-TIn the algorithm of Matula, an augmenting path is a path in the residual network, where a residual network is the network that remains after pruning the links of a previous augmenting path. There are no 1-hop paths fromu* to S, because then u*∈T. If u* has nT neighbors that belong to T, then there exist nT 2-hop paths from u* to S, for which either the first hop from u* to T or the second hop from T to S is part of the minimum cut. These nT paths form the first augmenting paths, after which λ(G)-nT remains. These remaining augmenting paths can be found in O(L) time each and since there are at most d(u*)-nT such paths, the complexity of the algorithm is bounded by O(NL). Finally, if λ(G)=δ(G), then the initialization guarantees that that value would be found.For directed multigraphs, Shiloach [44] provided a theorem that is stronger than Menger's theorem, namely.Theorem 13.
LetG be a directed k-link-connected multigraph, then for all s1,…,sk, t1,…,tk∈𝒩 (not necessarily distinct) there exist link-disjoint paths Pi from si to ti for i=1,…,k.We refer to Mansour and Schieber [45] for an O(NL)-time algorithm for determining the link connectivity in directed networks.For further reference, in Table2 we present some key achievements in computing minimum link cuts.Table 2
Related work on computing minimum link cuts.
Year
Reference
Complexity
Description
1971
Podderyugin[70]
O
(
N
L
)
Undirected graphs. Variation of Ford-Fulkerson max-flow algorithm in how augmenting paths of one and two hops are handled.
1971
Tarjan [67]
O
(
N
+
L
)
Testing for 2-link connectivity in undirected graphs via DFS.
1975
Even and Tarjan [29]
O
(
N
5
/
3
L
)
Application of Dinitz' algorithm.
1986
Karzanov and Timofeev [59]
O
(
λ
N
2
)
Undirected graphs.
1987
Matula [43]
O
(
N
L
), O(λN2)
Undirected graphs. It is also shown that the maximum subgraph link connectivity can be determined inO(N2L).
1989
Mansour and Schieber [45]
O
(
N
L
), O(λ2N2)
Directed graphs. Relation between minimum cut and dominating set.
1990
Nagamochi and Ibaraki [71]
O
(
L
+
λ
N
2
)
Undirected graphs. Algorithm does not use a max-flow algorithm.
1991
Galil and Italiano [72]
O
(
N
+
L
)
Testing for 3-link-connectivity in undirected graphs.
1991
Gabow [73]
O
(
λ
L
log
(
N
2
/
L
)
), O(L+λ2Nlog(N/λ))
Directed, resp. undirected graphs. Matroid approach.
1996
Karger [74]
O
(
L
log
2
N
)
Randomized algorithm.


## 2.1.1. Dinitz' Algorithm

Dinitz' algorithm, published in 1970 by Yefim Dinitz, was the first maximum-flow algorithm to run in polynomial time (contrary to the pseudopolynomial running time of the Ford-Fulkerson algorithm [24]). The algorithm is sometimes referred to as Dinic's or Dinits' algorithm, and also different variants are known. A historical perspective of the different variants is presented by Dinitz himself in [27]. In order to describe Dinitz' algorithm, as presented in Algorithm 1, some definitions are given.Algorithm 1:Dinitz-Max-Flow (G,c,s,t).
(
1
)  f(u,v)←0∀(u,v)∈ℒ and f*←0 /*Initialize to zero flow*/
(2) While /*loop until the algorithm terminates in line9*/
(3)For all nodes u∈𝒩, compute in Gf the hopcount h(u) to t /*by
Breadth-First-Search [28] from t*/
(4)Compute a blocking flow f in Gf thereby skipping links (u,v) for which
h(v)≠h(u)+1
(5)If f exists
(6)f*←f*+f
(7)Update Gf
(8)else
(9) return f*Definition 9.
The residual capacitycf(u,v) of a link (u,v) is interpreted in two directions as follows:
(2)cf(u,v)=c(u,v)-f(u,v),cf(v,u)=f(u,v),
where the flow f(u,v) over a link (u,v) cannot exceed the capacity c(u,v) of that link.Definition 10.
The residual graphGf of G is the graph in which a directed link (u,v) exists if cf(u,v)>0.Definition 11.
A blocking flowfb is an s-t flow such that any other s-t flow f would have to traverse a link already saturated by fb.A blocking flow could be obtained by repeatedly finding (via Depth-First-Search [28]) an  augmenting flow along an s-t path (or pruning the path from the graph in unit-capacity networks). In unit-capacity networks, the algorithm runs in O(L·(min{N2/3,L})), which therefore also is the time complexity to determine a minimum s-t link cut with Dinitz' algorithm (for unit node capacities, a complexity of O(LN) can be obtained [29]).For further reference, in Table1, we present some key achievements in computing minimum s-t link cuts.Table 1
Related work on computing minimums-t link cuts.
Year1
Reference
Complexity
Description
1951
Dantzig [30]
O
(
N
2
L
U
)
Linear programming, whereU is the largest link capacity.
1956
Ford and Fulkerson [31]
O
(
N
L
U
)
Augmenting paths.
1970
Dinitz [27]
O
(
N
2
L
), O(L·(min{N2/3,L}))
Resp. capacitated and unit-capacity graphs. Shortest augmenting paths.
1974
Karzanov [32]
O
(
N
3
)
Preflow-push (A simplification of Karzanov's algorithm has been presented by Tarjan [33]).
1980
Galil and Naamad [34]
O
(
N
L
log
2
N
)
Extension of Dinitz' algorithm.
1982
Shiloach and Vishkin [35]
O
(
(
N
3
log
N
)
/
p
)
Parallel algorithm forp≤N processors.
1983
Sleator and  Tarjan  [36]
O
(
N
L
log
N
)
Dynamic tree data structure.
1986
Goldberg and Tarjan [37]
O
(
N
L
log
(
N
2
/
L
)
)
Highest-label preflow-push.
1987
Ahuja et al. [38]
O
(
N
L
log
(
(
N
/
L
)
log
U
+
2
)
)
Excess scaling.
1989
Cheriyan and Hagerup [39]
O
(
N
L
+
N
2
log
3
N
)
Randomized algorithm.
1990
Alon [40]
O
(
N
L
)
Deterministic version of Cheriyan and Hagerup's randomized algorithm.
1998
Goldberg and Rao [41]
O
(
min
{
N
2
/
3
,
L
}
L
log
(
N
2
/
L
)
log
U
)
Length function.
2011
Christiano et al. [42]
O
~
(
L
N
1
/
3
ϵ
-
11
/
3
), O~(L+N4/3ϵ-8/3)
Resp.(1-ϵ) and (1+ϵ) approximation, where O~(f(x)) denotes O(f(x)logcf(x)) for some constant c.
1Throughout the paper, we take the convention of listing the year of the first (conference) publication, while referring to the extended (journal) version there where applicable.


## 2.1.2. Matula's Algorithm

In this section, we describe the algorithm from Matula [43] for determining the link connectivity of an undirected network. Matula's algorithm is based on the following lemma.Lemma 12.
LetG be a graph with a minimum cut of size λ(G)≤δ(G)-1 that partitions the graph G into two subgraphs G1(𝒩1,ℒ1) and G2(𝒩2,ℒ2), then any dominating set S of G contains nodes of both G1 and G2  (a dominating set S∈𝒩 is a subset of the nodes in G, such that every node in 𝒩 is either in S or adjacent to a node in S).Proof.
For subgraphGi, i=1,2, holds that the sum of the nodal degrees in Gi is bounded by
(3)Ni(Ni-1)+λ(G)≥∑u∈Gid(u)≥Niδ(G).
The upper bound occurs if all nodes in Gi are connected to each other and some of the nodes have a link that is part of the cut-set. The lower bound stems from each node having a degree larger or equal than the minimum degree δ(G). From the bounds in (3), we can derive that
(4)(Ni-δ(G))(Ni-1)≥δ(G)-λ(G).
Since λ(G)≤δ(G)-1 is assumed, (Ni-δ(G))(Ni-1)≥1 and consequently both terms on the left-hand side cannot be smaller than 1. Hence, Ni-δ(G)≥1, which means that, under the assumption that λ(G)≤δ(G)-1, there is at least one node in G1 that does not have a neighbor in G2 (and vice versa). In other words, any dominating set S of G should contain nodes of both G1 and G2.The algorithm of Matula (see Algorithm2) starts with a node of minimum degree (e.g., node s in G1) and gradually builds a dominating set S by adding nodes not yet part of or adjacent to the growing set. Since at one point a node, for example u*, from G2 needs to be added, keeping track of the minimum cut between newly added dominating nodes, and S will result in finding the overall minimum cut. The algorithm is presented below.Algorithm 2:Matula-Min-Cut (G).
(
1
) For a node s of minimum degree set S←{s}, T←{t∣t∈adj(s)}, U←𝒩-S-T, and λ←d(s).
(2) WhileU≠∅
(3) Choose u∈U
(4) n← The number of shortest augmenting paths from u to S
(5) If n<λ then λ←n
(6) Set S←S∪u, T←T∪{t∣t∈adj(u)}, followed by U←𝒩-S-TIn the algorithm of Matula, an augmenting path is a path in the residual network, where a residual network is the network that remains after pruning the links of a previous augmenting path. There are no 1-hop paths fromu* to S, because then u*∈T. If u* has nT neighbors that belong to T, then there exist nT 2-hop paths from u* to S, for which either the first hop from u* to T or the second hop from T to S is part of the minimum cut. These nT paths form the first augmenting paths, after which λ(G)-nT remains. These remaining augmenting paths can be found in O(L) time each and since there are at most d(u*)-nT such paths, the complexity of the algorithm is bounded by O(NL). Finally, if λ(G)=δ(G), then the initialization guarantees that that value would be found.For directed multigraphs, Shiloach [44] provided a theorem that is stronger than Menger's theorem, namely.Theorem 13.
LetG be a directed k-link-connected multigraph, then for all s1,…,sk, t1,…,tk∈𝒩 (not necessarily distinct) there exist link-disjoint paths Pi from si to ti for i=1,…,k.We refer to Mansour and Schieber [45] for an O(NL)-time algorithm for determining the link connectivity in directed networks.For further reference, in Table2 we present some key achievements in computing minimum link cuts.Table 2
Related work on computing minimum link cuts.
Year
Reference
Complexity
Description
1971
Podderyugin[70]
O
(
N
L
)
Undirected graphs. Variation of Ford-Fulkerson max-flow algorithm in how augmenting paths of one and two hops are handled.
1971
Tarjan [67]
O
(
N
+
L
)
Testing for 2-link connectivity in undirected graphs via DFS.
1975
Even and Tarjan [29]
O
(
N
5
/
3
L
)
Application of Dinitz' algorithm.
1986
Karzanov and Timofeev [59]
O
(
λ
N
2
)
Undirected graphs.
1987
Matula [43]
O
(
N
L
), O(λN2)
Undirected graphs. It is also shown that the maximum subgraph link connectivity can be determined inO(N2L).
1989
Mansour and Schieber [45]
O
(
N
L
), O(λ2N2)
Directed graphs. Relation between minimum cut and dominating set.
1990
Nagamochi and Ibaraki [71]
O
(
L
+
λ
N
2
)
Undirected graphs. Algorithm does not use a max-flow algorithm.
1991
Galil and Italiano [72]
O
(
N
+
L
)
Testing for 3-link-connectivity in undirected graphs.
1991
Gabow [73]
O
(
λ
L
log
(
N
2
/
L
)
), O(L+λ2Nlog(N/λ))
Directed, resp. undirected graphs. Matroid approach.
1996
Karger [74]
O
(
L
log
2
N
)
Randomized algorithm.


## 2.2. Determining Node Connectivity

Maximum-flow algorithms can also be used to determine the node connectivity, as demonstrated by Dantzig and Fulkerson [46] (and also discussed in [47]), by transforming the undirected graph G(𝒩,ℒ) to a directed graph G′(𝒩′,ℒ′) as follows.For every noden∈𝒩 place two nodes n′ and n′′ in 𝒩′ and connect them via a directed link (n′,n′′), using the convention that the link starts at n′ and ends at n′′. For every undirected link (i,j)∈ℒ place directed links (i′′,j′) and (j′′,i′) in G′. All links are assigned unit capacity.Thes-t node connectivity in G can be computed by finding a maximum flow from s′′ to t′ in G′. This can be seen as follows. Assume that there are κ node-disjoint paths between s and t, then there are also κ corresponding node-disjoint paths from s′′ to t′ in G′. Since each link has unit capacity, there thus exists a flow of at least κ. Since each link entering a node n′∈G′ has to traverse a single unit-capacity link (n′,n′′) at most one unit of flow can pass through a node, which corresponds to a node-disjoint path. Since there are only κ node-disjoint paths, the maximum flow in G′ is equal to κ.By using Dinitz' algorithm, one may compute thes-t node connectivity in O(L·(min{N2/3,L})) time, and by using the algorithm of Mansour and Schieber [45], the node connectivity can be determined in O(NL) time. We refer to Henzinger et al. [48] and Gabow [49] for more advanced algorithms to compute the node connectivity in directed and undirected graphs and to Yoshida and Ito [50] for a κ-node-connectivity property testing  algorithm (in property testing the objective is to decide, with high probability, whether the input graph is close to having a certain property. These algorithms typically run in sub-linear time).


## 3. Network Connectivity Augmentation

In the previous section, we have provided an overview of several algorithms to determine the connectivity of a network. In this section, we will overview several network augmentation algorithms that can be deployed to increase the connectivity (or some other metric) of a network by adding links. Network augmentation problems seem closely related to network deletion problems (e.g., see [51]), where the objective is to remove links in order to reach a certain property. However, there may be significant differences in terms of complexity. For instance, finding a minimum-weight set of links to cut a λ-link-connected graph such that its connectivity is reduced to λ=0 is solvable in polynomial time (as discussed in Section 2.1), while adding a minimum-weight set of links to increase a disconnected graph to λ-link-connectivity is NP-complete as shown in Section 3.1. When both link deletions and link additions are permitted, we speak of link modification problems, for example, see [52].


### 3.1. Link Connectivity Augmentation

In this section, we consider the following link augmentation problem.Problem 1 (the link connectivity augmentation (LCA) problem).
Given a graphG(𝒩,ℒ) consisting of N nodes and L links, link connectivity λ and an integer β, the link connectivity augmentation problem is to add a minimum-weight set of links, such that the link connectivity of the graph G is increased from λ to λ+β.We can discriminate several variants based on the graph (directed, simple, planar, etc.) or if link weights are used or not (i.e., in the unweighted case all links have weight 1). Let us start with the weighted link connectivity augmentation problem.Theorem 14.
The weighted LCA problem is NP-hard.We will use the proof due to Frederickson and JáJá [53] to show that the 3-dimensional matching (3DM) problem is reducible to the weighted LCA problem (an earlier proof has been provided by Eswaran and Tarjan [54], but since it aims to augment a network without any links to one that is 2 connected and has N links (a cycle), it has the characteristics of a design rather than an augmentation problem).Problem 2 (3-dimensional matching (3DM)).
Given a setM⊆X×Y×Z of triplets, where X, Y, and Z are disjoint sets of q elements each, is there a matching subset M′⊆M that contains all 3q elements, such that |M′|=q, and thus no two elements of M′ agree in any coordinate?Proof.
For a 3DM instanceM⊆X×Y×Z, with |M|=p, X={xi∣i=1,…,q}, Y={yi∣i=1,…,q}, and Z={zi∣i=1,…,q}, we create the graph G(𝒩,ℒ) of the corresponding instance of the weighted LCA problem as follows:
(5)𝒩={r}∪{xi,yi,zi∣i=1,…,q}∪{aijk,a-ijk∣(xi,yj,zk)∈M},ℒ={(r,xi),(r,yi),(r,zi)∣i=1,…,q}∪{(xi,aijk),(xi,a-ijk)∣(xi,yj,zk)∈M}.
The graph G as constructed above forms a tree and therefore is 1 connected. Links from the complement Gc of G can be used to augment the graph to 2-link connectivity. The weights of the links in Gc(𝒩,ℒc) are w(aijk,a-ijk)=w(yj,aijk)=w(zk,a-ijk)=1 for (xi,yj,zk)∈M, and for the remaining links in Gc, the weight is 2.
M contains a matching M′ if and only if there is a set ℒ′⊆ℒc of weight w(ℒ′)=p+q such that G′(𝒩,ℒ∪ℒ′) is 2-link connected. Assuming M′ exists, then adding links (yj,aijk) and (zk,a-ijk) for each triple (xi,yj,zk)∈M′ will establish the (2-connected) cycle r-yj-aijk-xi-a-ijk-zk-r. Since |M′|=q, the weight of these added links is 2q. The remaining nodes that are not yet on a cycle are the nodes aijk and a-ijk belonging to (xi,yj,zk)∈{M-M′}. These nodes will be directly connected, thereby creating the cycle xi-aijk-a-ijk-xi. In total, |M-M′|=p-q additional links will be added, leading to a total weight of links that have been added of p+q. Since the graph G is a tree with 2(p+q) leaves and the minimum link weight is 1, a network augmentation solution of weight p+q is indeed the lowest possible. It remains to demonstrate that an augmentation of weight p+q will lead to a valid matching M′. Since, in a solution of weight p+q, each leaf will be connected by precisely one link from ℒc, a link (yj,aijk) will prevent adding a link (aijk,a-ijk), and therefore also link (zk,a-ijk) must be added. The corresponding triple (xi,yj,zk) was not augmented before and is, therefore, part of a valid matching. The remaining p-q links (aijk,a-ijk) do not contribute to the matching.Frederickson and JáJá also used the construction of this proof to prove that the node-connectivity and strong-connectivity variants of the weighted LCA problem are NP-hard (in a directed graph strong connectivity is used, which means that there is a directed path from each node to every other node in the graph). We remark that the unweighted simple graph preserving LCA problem was claimed to be NP-hard by Jordán (reproduced in [55]) by using a reduction to one of the problems treated by Frederickson and JáJá. However, Jordán appears to be using an unweighted problem of which only (in the paper [53] referred to) the weighted version is proved to be NP-hard, and it is therefore not clear whether the unweighted problem is indeed NP-hard. For fixed β, the unweighted simple graph preserving problem can be solved in polynomial time [55].Eswaran and Tarjan [54] were the first to report on augmentation problems. They considered augmenting a network towards either 2-link connectivity, 2-node connectivity or strong connectivity, and provided for each unweighted problem variant an algorithm of complexity O(N+L)  (Raghavan [56] pointed out an error in the strong connectivity algorithm and provided a fix for it).  Since most protection schemes only focus on protecting against one single failure at a time (by finding two disjoint paths as discussed in Section 4), we will first present the 2-link-connectivity augmentation algorithm of Eswaran and Tarjan [54].


#### 3.1.1. Eswaran and Tarjan Algorithm

The algorithm of Eswaran and Tarjan as presented in Algorithm6 makes use of preorder (Algorithm 4) and postorder (Algorithm 3) numbering of nodes in a tree T (the label l(u) of node u denotes its number as a result of the ordering) and a procedure (Algorithm 5) to find 2-link-connected components.Algorithm 3:PostOrder (T,u,i).
(
1
) For each v←adj(u) do PostOrder (v,i)
(2)i←i+1
(3)l(u)←iAlgorithm 4:PreOrder (T,u,i).
(
1
)  i←i+1
(2)l(u)←i
(3) For eachv←adj(u) do PreOrder (v,i)Algorithm 5:Tarjan-2-link-components (G),
developed by Tarjan [57].
(
1
) Find a directed spanning tree T in G rooted at a node s
(2) PostOrder(T,s,0)
(3) Fori=1,…,N
(4)For j∈adj(i) /*Only nodes  “downstream”*/
(5)if min({i-ND(i)+1}∪{NL(j)}∪{j∣(i,j)∉T})>j-ND(j) and
max({i}∪{NH(j)}∪{j∣(i,j)∉T})≤j /*ND(i) is the number of descendants
in the tree including i*/
(6)  then (i,j) is 1-link-connected. /*Its removal cuts the graph*/Algorithm 6:Eswaran-Tarjan-2-link-augmentation (G).
(
1
) Find the 2-link-connected components of G
(2) CondenseG into a tree T for which each node represents one of the 2-link-
connected components ofG
(3) Number the nodes inT in preorder, starting from an arbitrary non-leaf node
s /*PreOrder (T,s,0)*/
(4) Fori=1,…,⌈r/2⌉ choose links (u(i),u(i+⌊r/2⌋)), where u(i),…,u(r) are the
r leaves of T ordered in increasing node number
(5) Map the ends of each chosen link to an arbitrary node in the corresponding
2-link-connected componentWe have assumed that the initial graph was connected. Eswaran and Tarjan's algorithm also allows to start with disconnected graphs, by augmenting the forest of condensed 2-link-connected components to a tree.


#### 3.1.2. Cactus Representation of All Minimum Cuts

The algorithm of Eswaran and Tarjan uses a tree representation of all the 2-link-connected components inG, which is subsequently used to find a proper augmentation. By using a so-called cactus representation of all minimum cuts in a network, a similar strategy could be deployed to augment a network to a connectivity >2. A graph G is defined to be a cactus graph if any two distinct simple cycles in G have at most one node in common (or equivalently, any link of G belongs to at most one cycle). In this section, we will present the cactus representation.We will use the notation(X,Y) to represent a set of links that connect nodes in X to nodes in Y. The link-set (X,X-), with X-=𝒩∖X, refers to a cut-set of links whose removal separates the graph into two subgraphs of nodes X and nodes X-. Dinitz et al. [58] have proposed a cactus structure ℋ(G) to represent all the minimum cuts of a graph G (possibly with parallel links) and have shown that there can be at most (N2) such minimum cuts. The structure ℋ(G) possesses the following properties.(1)
ℋ(G) is a cactus graph, that is, any two distinct simple cycles of ℋ(G) have at most one node in common.(2)
Each proper cut inℋ(G) is a minimum cut (a cut is called proper if the removal of the links in that cut partitions the graph in precisely two subgraphs. A minimum cut is always proper).(3)
For any link(u,v) that is part of a cycle in ℋ(G) the weight w(u,v)=λ/2, else w(u,v)=λ.(4)
w(λ(ℋ(G)))=λ(G), where w(λ(ℋ(G))) represents the minimum-weight link cut of ℋ(G).A cactus graph without cycles is a tree, and ifλ(G) is odd, then ℋ(G) is a tree. Cycles in the cactus graph ℋ(G) reflect so-called crossing cuts in G.Definition 15.
Two cuts(X,X-) and (Y,Y-), with X,Y∈𝒩, are crossing cuts, if all four sets X∩Y, X∩Y-, X-∩Y, and X-∩Y- are non-empty.Karzanov and Timofeev [59] have outlined an algorithm to compute ℋ(G) that consists of two parts: (1) computing all minimum cuts and (2) constructing the corresponding cactus representation. However, Nagamochi and Kameda [60] reported that their cactus representation may not be unique. We assume that all minimum cuts are already known (e.g., by computing minimum s-t cuts between all possible source-destination pairs, by the Gomory-Hu tree algorithm [61], or with Matula's algorithm as explained in [62]) and focus on explaining—by following the description of Fleischer [63]—how to build a unique cactus graph ℋ(G) for the graph G.Karzanov and Timofeev [59] observe that for a link (i,j)∈ℒ, any two minimum cuts (X,X-) and (Y,Y-) that separate i and j are nested, which means that X⊂Y (or vice versa). If we assign the nodes of G a preorder labelling {n1,…,nN}, such that node ni+1 is adjacent to a node in the set 𝒩i:={n1,…,ni}, and define ℳi to be the set of minimum cuts that contain 𝒩i-1 but not ni, then it follows that all cuts in ℳi are noncrossing for each i∈{2,…,N}. For instance, consider a 4-node ring {(a,b),(b,c),(c,d),(d,a)}, where three minimum cuts separate nodes a and d, namely, ({a},{b,c,d}), ({a,b},{c,d}), and ({a,b,c},{d}). Clearly {a}⊂{a,b}⊂{a,b,c}, which allows us to represent them as a path graph a-b-c-d. The three possibilities to cut this chain correspond to the three minimum cuts that separate a and d in the ring graph. For each ℳi there is a corresponding path graph Pi. These N-1 path graphs are used to create a single cactus graph. We proceed to present the algorithm as described by Fleischer [63] (for an alternative description we refer to [64]),  see Algorithm 7. We define η to be the function that maps nodes of G to nodes in ℋ(Gi+1), and we define Gi to be the graph G with nodes 𝒩i contracted to a single node (and any resulting self-loops removed). Let Gr be the smallest graph that has a minimum cut of value λ, where r corresponds to the largest index of such a graph. ℋ(Gr) is a path graph. The algorithm builds ℋ(Gi) from ℋ(Gi+1) until ℋ(G1)=ℋ(G) is obtained.Algorithm 7:Build-Cactus (G).
(
1
) Compute Pi for i=2,…,N
(2) Fori=r-1,…,1
(3)  Replace the nodeq in ℋ(Gi+1) that contains nodes {n1,…,ni+1} with the Path Pi+1.
IfPi+1=X1,…,Xk, then remove q and introduce k new nodes q1,…,qk with links
(qj,qj+1) for 1≤j<k.
(4)  Connect pathPi+1 to ℋ(Gi+1). For any tree or cycle link (q,w) in ℋ(Gi+1), let W≠∅
be the set of nodes inw, or if w is an empty node, the nodes in any nonempty
nodew' reachable from w by some path of links disjoint from a cycle containing
(q,w). Find the subset Xj such that w⊂Xj and connect W to qj.
(5)  Label the nodes ofPi+1. Let Q be the set of nodes mapped to q in ℋ(Gi+1).
Updateη by η-1(qj)∶=Xj∩Q for all 1≤j<k. All other mappings remain
unchanged.
(6)  Remove all empty nodes of degree≤2 and all empty 2-way cut nodes by contracting
an adjacent tree link (a node is anx-way cut node if its removal separates the graph into
x connected parts). Replace all empty 3-way cut nodes with 3 cycles.Figure1 gives an example of the execution of the algorithm on a 4-node ring.Figure 1
Example of a cactus construction for a 4-node ring topology. The top “row” gives the graphsGi, for i=1,…,r. The second row gives the paths Pi, for i=2,…,N. The third row presents the first iteration of the for loop in algorithm Build-Cactus, while the fourth row presents the last iteration. The last row presents the cactus representation of the ring, which is a ring itself.


#### 3.1.3. Naor-Gusfield-Martel Algorithm

Naor et al. [65] have proposed a polynomial-time algorithm to augment the link connectivity of a graph G from λ to λ+β, by adding the smallest number of (possibly parallel) links. The authors first demonstrate how to augment the link connectivity by one in O(NL) time, after which it is explained how executing this algorithm β times could optimally augment the graph towards λ+β link connectivity (Cheng and Jordán [66] further discuss link connectivity augmentation by adding one link at a time). In practice, as a result of the costs in network augmentation, a network's connectivity is likely not augmented with β>1. We will therefore only present the algorithm to augment the link connectivity by one, see Algorithm 9, and refer to [65] for the extended algorithm. The algorithm uses the cactus structure ℋ(G) that was presented in the previous section to represent all the minimum cuts of a graph G. The algorithm is similar in approach to the Eswaran-Tarjan algorithm, since a cactus representation of a 1-connected network is the tree representation used by Eswaran and Tarjan, and the algorithm connects “leafs” as Eswaran and Tarjan have done. Naor et al., however, use a different definition of leafs for cactus graphs.Definition 16 (cactus leaf).
A node in a cactus representationℋ(G) is a cactus leaf if it has degree 1 or is a cycle node of degree 2.Similarly to a tree, if the cactusℋ(G) has k leafs, then ⌈k/2⌉ links need to be added to increase the connectivity by 1.The algorithm uses a Depth-First-Search-like procedure, see Algorithm8, to label the nodes of the cactus graph.Algorithm 8:Cactus-DFS (ℋ(G)).
(
1
) Assign different colors to the different simple cycles /*, for example, by finding the articulation
points [67]*/
(2) DFS traversal that starts at an arbitrary node and obeys the following rule: if a nodeu is visited
for the first time via a cycle with some color, then traverse all other differently colored links
adjacent tou before traversing the adjacent link of the same color. Enumerate the cactus leafs
u1,…,uk in the order in which they are first encountered in the DFS traversal.Algorithm 9:Naor-Gusfield-Martel-Aug-1 (G).
(
1
)  ℋ(G)←Build-Cactus (G)
(2) Cactus-DFS(ℋ(G))
(3) Form the pairs{(Ui,Ui+⌈k/2⌉):1≤i≤⌊k/2⌋}, where Ui is the set of nodes from G
that map to the leafui of ℋ(G).
(4) For each pair(Ui,Ui+⌈k/2⌉):1≤i≤⌊k/2⌋, add a link between a node from G in Ui
and a node fromG in Ui+⌈k/2⌉. If k is odd, then connect a node in U⌈k/2⌉ to a node in
a different leafUj.For further reference, in Table3, we present some key achievements in augmenting link connectivity in unweighted graphs.Table 3
Related work on augmenting link connectivity in unweighted graphs.
Year
Reference
Complexity
Description
1976
Eswaran and Tarjan [54]
O
(
N
+
L
)
Augmenting to 2-connectivity.
1986
Cai and Sun [75]
NA
Splitting off links.
1987
Watanabe and Nakamura [76]
O
(
(
λ
+
β
)
2
N
4
(
(
λ
+
β
)
N
+
L
)
)
Based on a derived formula for the minimum number of links to(λ+β)-link-connect G.
1990
Frank [77]
O
(
N
6
)
Differents-t connectivities may be specified, instead of one (λ+β)-connectivity for all pairs1.
1990
Naor et al. [65]
O
(
β
2
N
L
+
β
3
N
2
+
N
C
flow
)
C
flow is the complexity of computing a maximum flow. If β=1, then the complexity is O(NL).
1991
Gabow [78]
O
(
L
+
(
λ
+
β
)
2
N
log
N
)
Poset representation of cuts applied to the Naor-Gusfield-Martel algorithm.
1994
Benczúr [79]
O
~
(
min
{
N
3
,
β
N
2
}
), O(N4)
Resp. randomized and deterministic algorithms.
1996
Nagamochi and Ibaraki [80]
O
(
N
(
L
+
N
log
N
)
log
N
)
Splitting off links.
1998
Benczúr and Karger [81]
O
(
N
2
log
8
N
)
Randomized algorithm.
2004
Nagamochi and Ibaraki [82]
O
(
N
L
+
N
2
log
N
)
Maximum adjacency ordering2.
1NP-hard variations of this problem and corresponding approximation results are provided by Nutov [83].
2Maximum adjacency ordering rule: add a new node ni+1 to previously selected nodes {n1,…,ni} that has the largest number of links to the set {n1,…,ni}. Start with an abitrary node n1.Splitting off a pair of links(u,v) and (v,w) refers to deleting those links and adding a new link (u,w). A pair of links is said to be splittable if the s-t min-cut values remain unaffected after splitting off the pair of links and is considered in the context of Mader's theorem.Theorem 17 (Mader [68, 69]).
LetG be a connected undirected graph where for some node s the degree d(s)≠3, and the removal of one of the adjacent links of s does not disconnect the graph, then s has a pair of splittable links.Mader's theorem has been used by for instance Cai and Sun [75] and Frank [77] in developing network augmentation algorithms. The algorithms (as already outlined in 1976 by Plesník [84]) attach a new node s to the graph with (λ+β) parallel links between s and all other nodes in the graph and subsequently proceed to split off splittable links.As indicated by Theorem14, the weighted LCA problem is NP-complete for both undirected graphs and directed graphs. Frederickson and JáJá [53] provided an O(N2) algorithm to make a weighted graph 2 connected. The algorithm is a 2-approximation algorithm if the starting graph is connected, else it is a 3-approximation algorithm. Khuller and Thurimella [85] proposed a 2-approximation algorithm for increasing the connectivity of a weighted undirected graph to (λ+β) that has a complexity of O(N(λ+β)logN(L+NlogN)). Taoka et al. [86] compare via simulations several approximation and heuristic algorithms, including their own maximum-weight-matching-based algorithm.Under specific conditions, the weighted LCA problem may be polynomially solvable, as shown by Frank [77] for the case that link weights are derived from node weights.


### 3.2. Node Connectivity Augmentation

In this section, we consider the following node augmentation problem.Problem 3.
The Node Connectivity Augmentation (NCA) problem. Given a graphG(𝒩,ℒ) consisting of N nodes and L links, node connectivity κ and an integer γ, the node connectivity augmentation problem is to add a minimum-weight set of links, such that the node connectivity of the graph G is increased from κ to κ+γ.Like for the LCA problem.Theorem 18.
The weighted NCA problem is NP-hard.Proof.
The proof of Theorem14 also applies here.The unweighted undirected NCA problem has received most attention. The specific case of making a graph 2-node connected was treated by Eswaran and Tarjan [54], Rosenthal and Goldner  [87]  (a correction to this algorithm has been made by Hsu and Ramachandran [88]). Watanabe and Nakamura [89] and Jordán [90] solved the case for achieving 3-node-connectivity, while Hsu [91] developed an algorithm to upgrade a 3-node connected graph to a 4-node-connected one. Increasing the connectivity of a κ-node-connected graph (where κ can be any integer) by 1 was studied by many researchers [90, 92–97], since it was long unknown whether the problem was polynomially solvable. In 2010, Végh [98] provided a polynomial-time algorithm to increase the connectivity of any κ-node-connected unweighted undirected graph by γ=1.Augmenting the node connectivity of directed graphs has been treated by Frank and Jordán [99]. They found a min-max formula that finds the minimum number of required new links to make an unweighted digraph (κ+γ)-node connected. Frank and Végh [100] developed a polynomial-time algorithm to make a κ-node-connected directed graph (κ+1)-node connected.As the weighted NCA problem is NP-complete, special cases have been considered [88–91, 98, 101]. Most of these articles discuss specific connectivity targets (γ and/or κ have specific values) or specific topologies, like trees. Also heuristic and approximation algorithms have been proposed [85, 102–107].


## 3.1. Link Connectivity Augmentation

In this section, we consider the following link augmentation problem.Problem 1 (the link connectivity augmentation (LCA) problem).
Given a graphG(𝒩,ℒ) consisting of N nodes and L links, link connectivity λ and an integer β, the link connectivity augmentation problem is to add a minimum-weight set of links, such that the link connectivity of the graph G is increased from λ to λ+β.We can discriminate several variants based on the graph (directed, simple, planar, etc.) or if link weights are used or not (i.e., in the unweighted case all links have weight 1). Let us start with the weighted link connectivity augmentation problem.Theorem 14.
The weighted LCA problem is NP-hard.We will use the proof due to Frederickson and JáJá [53] to show that the 3-dimensional matching (3DM) problem is reducible to the weighted LCA problem (an earlier proof has been provided by Eswaran and Tarjan [54], but since it aims to augment a network without any links to one that is 2 connected and has N links (a cycle), it has the characteristics of a design rather than an augmentation problem).Problem 2 (3-dimensional matching (3DM)).
Given a setM⊆X×Y×Z of triplets, where X, Y, and Z are disjoint sets of q elements each, is there a matching subset M′⊆M that contains all 3q elements, such that |M′|=q, and thus no two elements of M′ agree in any coordinate?Proof.
For a 3DM instanceM⊆X×Y×Z, with |M|=p, X={xi∣i=1,…,q}, Y={yi∣i=1,…,q}, and Z={zi∣i=1,…,q}, we create the graph G(𝒩,ℒ) of the corresponding instance of the weighted LCA problem as follows:
(5)𝒩={r}∪{xi,yi,zi∣i=1,…,q}∪{aijk,a-ijk∣(xi,yj,zk)∈M},ℒ={(r,xi),(r,yi),(r,zi)∣i=1,…,q}∪{(xi,aijk),(xi,a-ijk)∣(xi,yj,zk)∈M}.
The graph G as constructed above forms a tree and therefore is 1 connected. Links from the complement Gc of G can be used to augment the graph to 2-link connectivity. The weights of the links in Gc(𝒩,ℒc) are w(aijk,a-ijk)=w(yj,aijk)=w(zk,a-ijk)=1 for (xi,yj,zk)∈M, and for the remaining links in Gc, the weight is 2.
M contains a matching M′ if and only if there is a set ℒ′⊆ℒc of weight w(ℒ′)=p+q such that G′(𝒩,ℒ∪ℒ′) is 2-link connected. Assuming M′ exists, then adding links (yj,aijk) and (zk,a-ijk) for each triple (xi,yj,zk)∈M′ will establish the (2-connected) cycle r-yj-aijk-xi-a-ijk-zk-r. Since |M′|=q, the weight of these added links is 2q. The remaining nodes that are not yet on a cycle are the nodes aijk and a-ijk belonging to (xi,yj,zk)∈{M-M′}. These nodes will be directly connected, thereby creating the cycle xi-aijk-a-ijk-xi. In total, |M-M′|=p-q additional links will be added, leading to a total weight of links that have been added of p+q. Since the graph G is a tree with 2(p+q) leaves and the minimum link weight is 1, a network augmentation solution of weight p+q is indeed the lowest possible. It remains to demonstrate that an augmentation of weight p+q will lead to a valid matching M′. Since, in a solution of weight p+q, each leaf will be connected by precisely one link from ℒc, a link (yj,aijk) will prevent adding a link (aijk,a-ijk), and therefore also link (zk,a-ijk) must be added. The corresponding triple (xi,yj,zk) was not augmented before and is, therefore, part of a valid matching. The remaining p-q links (aijk,a-ijk) do not contribute to the matching.Frederickson and JáJá also used the construction of this proof to prove that the node-connectivity and strong-connectivity variants of the weighted LCA problem are NP-hard (in a directed graph strong connectivity is used, which means that there is a directed path from each node to every other node in the graph). We remark that the unweighted simple graph preserving LCA problem was claimed to be NP-hard by Jordán (reproduced in [55]) by using a reduction to one of the problems treated by Frederickson and JáJá. However, Jordán appears to be using an unweighted problem of which only (in the paper [53] referred to) the weighted version is proved to be NP-hard, and it is therefore not clear whether the unweighted problem is indeed NP-hard. For fixed β, the unweighted simple graph preserving problem can be solved in polynomial time [55].Eswaran and Tarjan [54] were the first to report on augmentation problems. They considered augmenting a network towards either 2-link connectivity, 2-node connectivity or strong connectivity, and provided for each unweighted problem variant an algorithm of complexity O(N+L)  (Raghavan [56] pointed out an error in the strong connectivity algorithm and provided a fix for it).  Since most protection schemes only focus on protecting against one single failure at a time (by finding two disjoint paths as discussed in Section 4), we will first present the 2-link-connectivity augmentation algorithm of Eswaran and Tarjan [54].


### 3.1.1. Eswaran and Tarjan Algorithm

The algorithm of Eswaran and Tarjan as presented in Algorithm6 makes use of preorder (Algorithm 4) and postorder (Algorithm 3) numbering of nodes in a tree T (the label l(u) of node u denotes its number as a result of the ordering) and a procedure (Algorithm 5) to find 2-link-connected components.Algorithm 3:PostOrder (T,u,i).
(
1
) For each v←adj(u) do PostOrder (v,i)
(2)i←i+1
(3)l(u)←iAlgorithm 4:PreOrder (T,u,i).
(
1
)  i←i+1
(2)l(u)←i
(3) For eachv←adj(u) do PreOrder (v,i)Algorithm 5:Tarjan-2-link-components (G),
developed by Tarjan [57].
(
1
) Find a directed spanning tree T in G rooted at a node s
(2) PostOrder(T,s,0)
(3) Fori=1,…,N
(4)For j∈adj(i) /*Only nodes  “downstream”*/
(5)if min({i-ND(i)+1}∪{NL(j)}∪{j∣(i,j)∉T})>j-ND(j) and
max({i}∪{NH(j)}∪{j∣(i,j)∉T})≤j /*ND(i) is the number of descendants
in the tree including i*/
(6)  then (i,j) is 1-link-connected. /*Its removal cuts the graph*/Algorithm 6:Eswaran-Tarjan-2-link-augmentation (G).
(
1
) Find the 2-link-connected components of G
(2) CondenseG into a tree T for which each node represents one of the 2-link-
connected components ofG
(3) Number the nodes inT in preorder, starting from an arbitrary non-leaf node
s /*PreOrder (T,s,0)*/
(4) Fori=1,…,⌈r/2⌉ choose links (u(i),u(i+⌊r/2⌋)), where u(i),…,u(r) are the
r leaves of T ordered in increasing node number
(5) Map the ends of each chosen link to an arbitrary node in the corresponding
2-link-connected componentWe have assumed that the initial graph was connected. Eswaran and Tarjan's algorithm also allows to start with disconnected graphs, by augmenting the forest of condensed 2-link-connected components to a tree.


### 3.1.2. Cactus Representation of All Minimum Cuts

The algorithm of Eswaran and Tarjan uses a tree representation of all the 2-link-connected components inG, which is subsequently used to find a proper augmentation. By using a so-called cactus representation of all minimum cuts in a network, a similar strategy could be deployed to augment a network to a connectivity >2. A graph G is defined to be a cactus graph if any two distinct simple cycles in G have at most one node in common (or equivalently, any link of G belongs to at most one cycle). In this section, we will present the cactus representation.We will use the notation(X,Y) to represent a set of links that connect nodes in X to nodes in Y. The link-set (X,X-), with X-=𝒩∖X, refers to a cut-set of links whose removal separates the graph into two subgraphs of nodes X and nodes X-. Dinitz et al. [58] have proposed a cactus structure ℋ(G) to represent all the minimum cuts of a graph G (possibly with parallel links) and have shown that there can be at most (N2) such minimum cuts. The structure ℋ(G) possesses the following properties.(1)
ℋ(G) is a cactus graph, that is, any two distinct simple cycles of ℋ(G) have at most one node in common.(2)
Each proper cut inℋ(G) is a minimum cut (a cut is called proper if the removal of the links in that cut partitions the graph in precisely two subgraphs. A minimum cut is always proper).(3)
For any link(u,v) that is part of a cycle in ℋ(G) the weight w(u,v)=λ/2, else w(u,v)=λ.(4)
w(λ(ℋ(G)))=λ(G), where w(λ(ℋ(G))) represents the minimum-weight link cut of ℋ(G).A cactus graph without cycles is a tree, and ifλ(G) is odd, then ℋ(G) is a tree. Cycles in the cactus graph ℋ(G) reflect so-called crossing cuts in G.Definition 15.
Two cuts(X,X-) and (Y,Y-), with X,Y∈𝒩, are crossing cuts, if all four sets X∩Y, X∩Y-, X-∩Y, and X-∩Y- are non-empty.Karzanov and Timofeev [59] have outlined an algorithm to compute ℋ(G) that consists of two parts: (1) computing all minimum cuts and (2) constructing the corresponding cactus representation. However, Nagamochi and Kameda [60] reported that their cactus representation may not be unique. We assume that all minimum cuts are already known (e.g., by computing minimum s-t cuts between all possible source-destination pairs, by the Gomory-Hu tree algorithm [61], or with Matula's algorithm as explained in [62]) and focus on explaining—by following the description of Fleischer [63]—how to build a unique cactus graph ℋ(G) for the graph G.Karzanov and Timofeev [59] observe that for a link (i,j)∈ℒ, any two minimum cuts (X,X-) and (Y,Y-) that separate i and j are nested, which means that X⊂Y (or vice versa). If we assign the nodes of G a preorder labelling {n1,…,nN}, such that node ni+1 is adjacent to a node in the set 𝒩i:={n1,…,ni}, and define ℳi to be the set of minimum cuts that contain 𝒩i-1 but not ni, then it follows that all cuts in ℳi are noncrossing for each i∈{2,…,N}. For instance, consider a 4-node ring {(a,b),(b,c),(c,d),(d,a)}, where three minimum cuts separate nodes a and d, namely, ({a},{b,c,d}), ({a,b},{c,d}), and ({a,b,c},{d}). Clearly {a}⊂{a,b}⊂{a,b,c}, which allows us to represent them as a path graph a-b-c-d. The three possibilities to cut this chain correspond to the three minimum cuts that separate a and d in the ring graph. For each ℳi there is a corresponding path graph Pi. These N-1 path graphs are used to create a single cactus graph. We proceed to present the algorithm as described by Fleischer [63] (for an alternative description we refer to [64]),  see Algorithm 7. We define η to be the function that maps nodes of G to nodes in ℋ(Gi+1), and we define Gi to be the graph G with nodes 𝒩i contracted to a single node (and any resulting self-loops removed). Let Gr be the smallest graph that has a minimum cut of value λ, where r corresponds to the largest index of such a graph. ℋ(Gr) is a path graph. The algorithm builds ℋ(Gi) from ℋ(Gi+1) until ℋ(G1)=ℋ(G) is obtained.Algorithm 7:Build-Cactus (G).
(
1
) Compute Pi for i=2,…,N
(2) Fori=r-1,…,1
(3)  Replace the nodeq in ℋ(Gi+1) that contains nodes {n1,…,ni+1} with the Path Pi+1.
IfPi+1=X1,…,Xk, then remove q and introduce k new nodes q1,…,qk with links
(qj,qj+1) for 1≤j<k.
(4)  Connect pathPi+1 to ℋ(Gi+1). For any tree or cycle link (q,w) in ℋ(Gi+1), let W≠∅
be the set of nodes inw, or if w is an empty node, the nodes in any nonempty
nodew' reachable from w by some path of links disjoint from a cycle containing
(q,w). Find the subset Xj such that w⊂Xj and connect W to qj.
(5)  Label the nodes ofPi+1. Let Q be the set of nodes mapped to q in ℋ(Gi+1).
Updateη by η-1(qj)∶=Xj∩Q for all 1≤j<k. All other mappings remain
unchanged.
(6)  Remove all empty nodes of degree≤2 and all empty 2-way cut nodes by contracting
an adjacent tree link (a node is anx-way cut node if its removal separates the graph into
x connected parts). Replace all empty 3-way cut nodes with 3 cycles.Figure1 gives an example of the execution of the algorithm on a 4-node ring.Figure 1
Example of a cactus construction for a 4-node ring topology. The top “row” gives the graphsGi, for i=1,…,r. The second row gives the paths Pi, for i=2,…,N. The third row presents the first iteration of the for loop in algorithm Build-Cactus, while the fourth row presents the last iteration. The last row presents the cactus representation of the ring, which is a ring itself.


### 3.1.3. Naor-Gusfield-Martel Algorithm

Naor et al. [65] have proposed a polynomial-time algorithm to augment the link connectivity of a graph G from λ to λ+β, by adding the smallest number of (possibly parallel) links. The authors first demonstrate how to augment the link connectivity by one in O(NL) time, after which it is explained how executing this algorithm β times could optimally augment the graph towards λ+β link connectivity (Cheng and Jordán [66] further discuss link connectivity augmentation by adding one link at a time). In practice, as a result of the costs in network augmentation, a network's connectivity is likely not augmented with β>1. We will therefore only present the algorithm to augment the link connectivity by one, see Algorithm 9, and refer to [65] for the extended algorithm. The algorithm uses the cactus structure ℋ(G) that was presented in the previous section to represent all the minimum cuts of a graph G. The algorithm is similar in approach to the Eswaran-Tarjan algorithm, since a cactus representation of a 1-connected network is the tree representation used by Eswaran and Tarjan, and the algorithm connects “leafs” as Eswaran and Tarjan have done. Naor et al., however, use a different definition of leafs for cactus graphs.Definition 16 (cactus leaf).
A node in a cactus representationℋ(G) is a cactus leaf if it has degree 1 or is a cycle node of degree 2.Similarly to a tree, if the cactusℋ(G) has k leafs, then ⌈k/2⌉ links need to be added to increase the connectivity by 1.The algorithm uses a Depth-First-Search-like procedure, see Algorithm8, to label the nodes of the cactus graph.Algorithm 8:Cactus-DFS (ℋ(G)).
(
1
) Assign different colors to the different simple cycles /*, for example, by finding the articulation
points [67]*/
(2) DFS traversal that starts at an arbitrary node and obeys the following rule: if a nodeu is visited
for the first time via a cycle with some color, then traverse all other differently colored links
adjacent tou before traversing the adjacent link of the same color. Enumerate the cactus leafs
u1,…,uk in the order in which they are first encountered in the DFS traversal.Algorithm 9:Naor-Gusfield-Martel-Aug-1 (G).
(
1
)  ℋ(G)←Build-Cactus (G)
(2) Cactus-DFS(ℋ(G))
(3) Form the pairs{(Ui,Ui+⌈k/2⌉):1≤i≤⌊k/2⌋}, where Ui is the set of nodes from G
that map to the leafui of ℋ(G).
(4) For each pair(Ui,Ui+⌈k/2⌉):1≤i≤⌊k/2⌋, add a link between a node from G in Ui
and a node fromG in Ui+⌈k/2⌉. If k is odd, then connect a node in U⌈k/2⌉ to a node in
a different leafUj.For further reference, in Table3, we present some key achievements in augmenting link connectivity in unweighted graphs.Table 3
Related work on augmenting link connectivity in unweighted graphs.
Year
Reference
Complexity
Description
1976
Eswaran and Tarjan [54]
O
(
N
+
L
)
Augmenting to 2-connectivity.
1986
Cai and Sun [75]
NA
Splitting off links.
1987
Watanabe and Nakamura [76]
O
(
(
λ
+
β
)
2
N
4
(
(
λ
+
β
)
N
+
L
)
)
Based on a derived formula for the minimum number of links to(λ+β)-link-connect G.
1990
Frank [77]
O
(
N
6
)
Differents-t connectivities may be specified, instead of one (λ+β)-connectivity for all pairs1.
1990
Naor et al. [65]
O
(
β
2
N
L
+
β
3
N
2
+
N
C
flow
)
C
flow is the complexity of computing a maximum flow. If β=1, then the complexity is O(NL).
1991
Gabow [78]
O
(
L
+
(
λ
+
β
)
2
N
log
N
)
Poset representation of cuts applied to the Naor-Gusfield-Martel algorithm.
1994
Benczúr [79]
O
~
(
min
{
N
3
,
β
N
2
}
), O(N4)
Resp. randomized and deterministic algorithms.
1996
Nagamochi and Ibaraki [80]
O
(
N
(
L
+
N
log
N
)
log
N
)
Splitting off links.
1998
Benczúr and Karger [81]
O
(
N
2
log
8
N
)
Randomized algorithm.
2004
Nagamochi and Ibaraki [82]
O
(
N
L
+
N
2
log
N
)
Maximum adjacency ordering2.
1NP-hard variations of this problem and corresponding approximation results are provided by Nutov [83].
2Maximum adjacency ordering rule: add a new node ni+1 to previously selected nodes {n1,…,ni} that has the largest number of links to the set {n1,…,ni}. Start with an abitrary node n1.Splitting off a pair of links(u,v) and (v,w) refers to deleting those links and adding a new link (u,w). A pair of links is said to be splittable if the s-t min-cut values remain unaffected after splitting off the pair of links and is considered in the context of Mader's theorem.Theorem 17 (Mader [68, 69]).
LetG be a connected undirected graph where for some node s the degree d(s)≠3, and the removal of one of the adjacent links of s does not disconnect the graph, then s has a pair of splittable links.Mader's theorem has been used by for instance Cai and Sun [75] and Frank [77] in developing network augmentation algorithms. The algorithms (as already outlined in 1976 by Plesník [84]) attach a new node s to the graph with (λ+β) parallel links between s and all other nodes in the graph and subsequently proceed to split off splittable links.As indicated by Theorem14, the weighted LCA problem is NP-complete for both undirected graphs and directed graphs. Frederickson and JáJá [53] provided an O(N2) algorithm to make a weighted graph 2 connected. The algorithm is a 2-approximation algorithm if the starting graph is connected, else it is a 3-approximation algorithm. Khuller and Thurimella [85] proposed a 2-approximation algorithm for increasing the connectivity of a weighted undirected graph to (λ+β) that has a complexity of O(N(λ+β)logN(L+NlogN)). Taoka et al. [86] compare via simulations several approximation and heuristic algorithms, including their own maximum-weight-matching-based algorithm.Under specific conditions, the weighted LCA problem may be polynomially solvable, as shown by Frank [77] for the case that link weights are derived from node weights.


## 3.1.1. Eswaran and Tarjan Algorithm

The algorithm of Eswaran and Tarjan as presented in Algorithm6 makes use of preorder (Algorithm 4) and postorder (Algorithm 3) numbering of nodes in a tree T (the label l(u) of node u denotes its number as a result of the ordering) and a procedure (Algorithm 5) to find 2-link-connected components.Algorithm 3:PostOrder (T,u,i).
(
1
) For each v←adj(u) do PostOrder (v,i)
(2)i←i+1
(3)l(u)←iAlgorithm 4:PreOrder (T,u,i).
(
1
)  i←i+1
(2)l(u)←i
(3) For eachv←adj(u) do PreOrder (v,i)Algorithm 5:Tarjan-2-link-components (G),
developed by Tarjan [57].
(
1
) Find a directed spanning tree T in G rooted at a node s
(2) PostOrder(T,s,0)
(3) Fori=1,…,N
(4)For j∈adj(i) /*Only nodes  “downstream”*/
(5)if min({i-ND(i)+1}∪{NL(j)}∪{j∣(i,j)∉T})>j-ND(j) and
max({i}∪{NH(j)}∪{j∣(i,j)∉T})≤j /*ND(i) is the number of descendants
in the tree including i*/
(6)  then (i,j) is 1-link-connected. /*Its removal cuts the graph*/Algorithm 6:Eswaran-Tarjan-2-link-augmentation (G).
(
1
) Find the 2-link-connected components of G
(2) CondenseG into a tree T for which each node represents one of the 2-link-
connected components ofG
(3) Number the nodes inT in preorder, starting from an arbitrary non-leaf node
s /*PreOrder (T,s,0)*/
(4) Fori=1,…,⌈r/2⌉ choose links (u(i),u(i+⌊r/2⌋)), where u(i),…,u(r) are the
r leaves of T ordered in increasing node number
(5) Map the ends of each chosen link to an arbitrary node in the corresponding
2-link-connected componentWe have assumed that the initial graph was connected. Eswaran and Tarjan's algorithm also allows to start with disconnected graphs, by augmenting the forest of condensed 2-link-connected components to a tree.


## 3.1.2. Cactus Representation of All Minimum Cuts

The algorithm of Eswaran and Tarjan uses a tree representation of all the 2-link-connected components inG, which is subsequently used to find a proper augmentation. By using a so-called cactus representation of all minimum cuts in a network, a similar strategy could be deployed to augment a network to a connectivity >2. A graph G is defined to be a cactus graph if any two distinct simple cycles in G have at most one node in common (or equivalently, any link of G belongs to at most one cycle). In this section, we will present the cactus representation.We will use the notation(X,Y) to represent a set of links that connect nodes in X to nodes in Y. The link-set (X,X-), with X-=𝒩∖X, refers to a cut-set of links whose removal separates the graph into two subgraphs of nodes X and nodes X-. Dinitz et al. [58] have proposed a cactus structure ℋ(G) to represent all the minimum cuts of a graph G (possibly with parallel links) and have shown that there can be at most (N2) such minimum cuts. The structure ℋ(G) possesses the following properties.(1)
ℋ(G) is a cactus graph, that is, any two distinct simple cycles of ℋ(G) have at most one node in common.(2)
Each proper cut inℋ(G) is a minimum cut (a cut is called proper if the removal of the links in that cut partitions the graph in precisely two subgraphs. A minimum cut is always proper).(3)
For any link(u,v) that is part of a cycle in ℋ(G) the weight w(u,v)=λ/2, else w(u,v)=λ.(4)
w(λ(ℋ(G)))=λ(G), where w(λ(ℋ(G))) represents the minimum-weight link cut of ℋ(G).A cactus graph without cycles is a tree, and ifλ(G) is odd, then ℋ(G) is a tree. Cycles in the cactus graph ℋ(G) reflect so-called crossing cuts in G.Definition 15.
Two cuts(X,X-) and (Y,Y-), with X,Y∈𝒩, are crossing cuts, if all four sets X∩Y, X∩Y-, X-∩Y, and X-∩Y- are non-empty.Karzanov and Timofeev [59] have outlined an algorithm to compute ℋ(G) that consists of two parts: (1) computing all minimum cuts and (2) constructing the corresponding cactus representation. However, Nagamochi and Kameda [60] reported that their cactus representation may not be unique. We assume that all minimum cuts are already known (e.g., by computing minimum s-t cuts between all possible source-destination pairs, by the Gomory-Hu tree algorithm [61], or with Matula's algorithm as explained in [62]) and focus on explaining—by following the description of Fleischer [63]—how to build a unique cactus graph ℋ(G) for the graph G.Karzanov and Timofeev [59] observe that for a link (i,j)∈ℒ, any two minimum cuts (X,X-) and (Y,Y-) that separate i and j are nested, which means that X⊂Y (or vice versa). If we assign the nodes of G a preorder labelling {n1,…,nN}, such that node ni+1 is adjacent to a node in the set 𝒩i:={n1,…,ni}, and define ℳi to be the set of minimum cuts that contain 𝒩i-1 but not ni, then it follows that all cuts in ℳi are noncrossing for each i∈{2,…,N}. For instance, consider a 4-node ring {(a,b),(b,c),(c,d),(d,a)}, where three minimum cuts separate nodes a and d, namely, ({a},{b,c,d}), ({a,b},{c,d}), and ({a,b,c},{d}). Clearly {a}⊂{a,b}⊂{a,b,c}, which allows us to represent them as a path graph a-b-c-d. The three possibilities to cut this chain correspond to the three minimum cuts that separate a and d in the ring graph. For each ℳi there is a corresponding path graph Pi. These N-1 path graphs are used to create a single cactus graph. We proceed to present the algorithm as described by Fleischer [63] (for an alternative description we refer to [64]),  see Algorithm 7. We define η to be the function that maps nodes of G to nodes in ℋ(Gi+1), and we define Gi to be the graph G with nodes 𝒩i contracted to a single node (and any resulting self-loops removed). Let Gr be the smallest graph that has a minimum cut of value λ, where r corresponds to the largest index of such a graph. ℋ(Gr) is a path graph. The algorithm builds ℋ(Gi) from ℋ(Gi+1) until ℋ(G1)=ℋ(G) is obtained.Algorithm 7:Build-Cactus (G).
(
1
) Compute Pi for i=2,…,N
(2) Fori=r-1,…,1
(3)  Replace the nodeq in ℋ(Gi+1) that contains nodes {n1,…,ni+1} with the Path Pi+1.
IfPi+1=X1,…,Xk, then remove q and introduce k new nodes q1,…,qk with links
(qj,qj+1) for 1≤j<k.
(4)  Connect pathPi+1 to ℋ(Gi+1). For any tree or cycle link (q,w) in ℋ(Gi+1), let W≠∅
be the set of nodes inw, or if w is an empty node, the nodes in any nonempty
nodew' reachable from w by some path of links disjoint from a cycle containing
(q,w). Find the subset Xj such that w⊂Xj and connect W to qj.
(5)  Label the nodes ofPi+1. Let Q be the set of nodes mapped to q in ℋ(Gi+1).
Updateη by η-1(qj)∶=Xj∩Q for all 1≤j<k. All other mappings remain
unchanged.
(6)  Remove all empty nodes of degree≤2 and all empty 2-way cut nodes by contracting
an adjacent tree link (a node is anx-way cut node if its removal separates the graph into
x connected parts). Replace all empty 3-way cut nodes with 3 cycles.Figure1 gives an example of the execution of the algorithm on a 4-node ring.Figure 1
Example of a cactus construction for a 4-node ring topology. The top “row” gives the graphsGi, for i=1,…,r. The second row gives the paths Pi, for i=2,…,N. The third row presents the first iteration of the for loop in algorithm Build-Cactus, while the fourth row presents the last iteration. The last row presents the cactus representation of the ring, which is a ring itself.


## 3.1.3. Naor-Gusfield-Martel Algorithm

Naor et al. [65] have proposed a polynomial-time algorithm to augment the link connectivity of a graph G from λ to λ+β, by adding the smallest number of (possibly parallel) links. The authors first demonstrate how to augment the link connectivity by one in O(NL) time, after which it is explained how executing this algorithm β times could optimally augment the graph towards λ+β link connectivity (Cheng and Jordán [66] further discuss link connectivity augmentation by adding one link at a time). In practice, as a result of the costs in network augmentation, a network's connectivity is likely not augmented with β>1. We will therefore only present the algorithm to augment the link connectivity by one, see Algorithm 9, and refer to [65] for the extended algorithm. The algorithm uses the cactus structure ℋ(G) that was presented in the previous section to represent all the minimum cuts of a graph G. The algorithm is similar in approach to the Eswaran-Tarjan algorithm, since a cactus representation of a 1-connected network is the tree representation used by Eswaran and Tarjan, and the algorithm connects “leafs” as Eswaran and Tarjan have done. Naor et al., however, use a different definition of leafs for cactus graphs.Definition 16 (cactus leaf).
A node in a cactus representationℋ(G) is a cactus leaf if it has degree 1 or is a cycle node of degree 2.Similarly to a tree, if the cactusℋ(G) has k leafs, then ⌈k/2⌉ links need to be added to increase the connectivity by 1.The algorithm uses a Depth-First-Search-like procedure, see Algorithm8, to label the nodes of the cactus graph.Algorithm 8:Cactus-DFS (ℋ(G)).
(
1
) Assign different colors to the different simple cycles /*, for example, by finding the articulation
points [67]*/
(2) DFS traversal that starts at an arbitrary node and obeys the following rule: if a nodeu is visited
for the first time via a cycle with some color, then traverse all other differently colored links
adjacent tou before traversing the adjacent link of the same color. Enumerate the cactus leafs
u1,…,uk in the order in which they are first encountered in the DFS traversal.Algorithm 9:Naor-Gusfield-Martel-Aug-1 (G).
(
1
)  ℋ(G)←Build-Cactus (G)
(2) Cactus-DFS(ℋ(G))
(3) Form the pairs{(Ui,Ui+⌈k/2⌉):1≤i≤⌊k/2⌋}, where Ui is the set of nodes from G
that map to the leafui of ℋ(G).
(4) For each pair(Ui,Ui+⌈k/2⌉):1≤i≤⌊k/2⌋, add a link between a node from G in Ui
and a node fromG in Ui+⌈k/2⌉. If k is odd, then connect a node in U⌈k/2⌉ to a node in
a different leafUj.For further reference, in Table3, we present some key achievements in augmenting link connectivity in unweighted graphs.Table 3
Related work on augmenting link connectivity in unweighted graphs.
Year
Reference
Complexity
Description
1976
Eswaran and Tarjan [54]
O
(
N
+
L
)
Augmenting to 2-connectivity.
1986
Cai and Sun [75]
NA
Splitting off links.
1987
Watanabe and Nakamura [76]
O
(
(
λ
+
β
)
2
N
4
(
(
λ
+
β
)
N
+
L
)
)
Based on a derived formula for the minimum number of links to(λ+β)-link-connect G.
1990
Frank [77]
O
(
N
6
)
Differents-t connectivities may be specified, instead of one (λ+β)-connectivity for all pairs1.
1990
Naor et al. [65]
O
(
β
2
N
L
+
β
3
N
2
+
N
C
flow
)
C
flow is the complexity of computing a maximum flow. If β=1, then the complexity is O(NL).
1991
Gabow [78]
O
(
L
+
(
λ
+
β
)
2
N
log
N
)
Poset representation of cuts applied to the Naor-Gusfield-Martel algorithm.
1994
Benczúr [79]
O
~
(
min
{
N
3
,
β
N
2
}
), O(N4)
Resp. randomized and deterministic algorithms.
1996
Nagamochi and Ibaraki [80]
O
(
N
(
L
+
N
log
N
)
log
N
)
Splitting off links.
1998
Benczúr and Karger [81]
O
(
N
2
log
8
N
)
Randomized algorithm.
2004
Nagamochi and Ibaraki [82]
O
(
N
L
+
N
2
log
N
)
Maximum adjacency ordering2.
1NP-hard variations of this problem and corresponding approximation results are provided by Nutov [83].
2Maximum adjacency ordering rule: add a new node ni+1 to previously selected nodes {n1,…,ni} that has the largest number of links to the set {n1,…,ni}. Start with an abitrary node n1.Splitting off a pair of links(u,v) and (v,w) refers to deleting those links and adding a new link (u,w). A pair of links is said to be splittable if the s-t min-cut values remain unaffected after splitting off the pair of links and is considered in the context of Mader's theorem.Theorem 17 (Mader [68, 69]).
LetG be a connected undirected graph where for some node s the degree d(s)≠3, and the removal of one of the adjacent links of s does not disconnect the graph, then s has a pair of splittable links.Mader's theorem has been used by for instance Cai and Sun [75] and Frank [77] in developing network augmentation algorithms. The algorithms (as already outlined in 1976 by Plesník [84]) attach a new node s to the graph with (λ+β) parallel links between s and all other nodes in the graph and subsequently proceed to split off splittable links.As indicated by Theorem14, the weighted LCA problem is NP-complete for both undirected graphs and directed graphs. Frederickson and JáJá [53] provided an O(N2) algorithm to make a weighted graph 2 connected. The algorithm is a 2-approximation algorithm if the starting graph is connected, else it is a 3-approximation algorithm. Khuller and Thurimella [85] proposed a 2-approximation algorithm for increasing the connectivity of a weighted undirected graph to (λ+β) that has a complexity of O(N(λ+β)logN(L+NlogN)). Taoka et al. [86] compare via simulations several approximation and heuristic algorithms, including their own maximum-weight-matching-based algorithm.Under specific conditions, the weighted LCA problem may be polynomially solvable, as shown by Frank [77] for the case that link weights are derived from node weights.


## 3.2. Node Connectivity Augmentation

In this section, we consider the following node augmentation problem.Problem 3.
The Node Connectivity Augmentation (NCA) problem. Given a graphG(𝒩,ℒ) consisting of N nodes and L links, node connectivity κ and an integer γ, the node connectivity augmentation problem is to add a minimum-weight set of links, such that the node connectivity of the graph G is increased from κ to κ+γ.Like for the LCA problem.Theorem 18.
The weighted NCA problem is NP-hard.Proof.
The proof of Theorem14 also applies here.The unweighted undirected NCA problem has received most attention. The specific case of making a graph 2-node connected was treated by Eswaran and Tarjan [54], Rosenthal and Goldner  [87]  (a correction to this algorithm has been made by Hsu and Ramachandran [88]). Watanabe and Nakamura [89] and Jordán [90] solved the case for achieving 3-node-connectivity, while Hsu [91] developed an algorithm to upgrade a 3-node connected graph to a 4-node-connected one. Increasing the connectivity of a κ-node-connected graph (where κ can be any integer) by 1 was studied by many researchers [90, 92–97], since it was long unknown whether the problem was polynomially solvable. In 2010, Végh [98] provided a polynomial-time algorithm to increase the connectivity of any κ-node-connected unweighted undirected graph by γ=1.Augmenting the node connectivity of directed graphs has been treated by Frank and Jordán [99]. They found a min-max formula that finds the minimum number of required new links to make an unweighted digraph (κ+γ)-node connected. Frank and Végh [100] developed a polynomial-time algorithm to make a κ-node-connected directed graph (κ+1)-node connected.As the weighted NCA problem is NP-complete, special cases have been considered [88–91, 98, 101]. Most of these articles discuss specific connectivity targets (γ and/or κ have specific values) or specific topologies, like trees. Also heuristic and approximation algorithms have been proposed [85, 102–107].


## 4. Disjoint Paths

When a network is (made to be) robust, algorithms should be in place that can find link- or node-disjoint paths to protect against a link or node failure. There can be several objectives associated with finding link- or node-disjoint paths.Problem 4.
Given a graphG(𝒩,ℒ), where |𝒩|=N and |ℒ|=L, a weight w(u,v) and a capacity c(u,v) associated with each link (u,v)∈ℒ, a source node s and a terminal node t, and two bounds Δ1≥0 and Δ2≥0 find a pair of disjoint paths from s to t such as the following.Min-Sum Disjoint Paths Problem
The total weight of the pair of disjoint paths is minimized.Min-Max Disjoint Paths Problem
The maximum path weight of the two disjoint paths is minimized.Min-Min Disjoint Paths Problem
The smallest path weight of the two disjoint paths is minimized.Bounded Disjoint Paths Problem
The weight of the primary path should be less than or equal toΔ1, and the weight of the backup path should be less than or equal to Δ2.Widest Disjoint Paths Problem
The smallest capacity over all links in the two paths is maximized.The most common and simpler one is themin-sum disjoint paths problem. If the two paths are used simultaneously for load-balancing purposes (or 1+1 protection), then the min-max objective is desirable. Unfortunately, the min-max disjoint paths problem is NP-hard [108]. If failures are expected to occur only sporadically (and in case of 1 : 1 protection), then it may be desirable to minimize the weight of the primary (shorter) path (min-min objective), which also leads to an NP-hard problem [109]. The min-max and min-min disjoint paths problems could be considered as extreme cases of the bounded disjoint paths problem, which was shown to be NP-hard [110] and later proven to be APX-hard by Bley [111] (the graph structure referred to as lobe that was used by Itai et al. [110] to prove NP-completeness has since often been used to prove that other disjoint paths problems are NP-complete, e.g., [112–114]). Finding widest disjoint paths can easily be done by pruning “low-capacity” links from the graph and finding disjoint paths. When the capacity requirements for the primary and backup paths are different, disjoint paths problems usually become NP-complete [115].Beshir and Kuipers [116] investigated the min-sum disjoint paths problem with min-max, min-min, bounded, and widest, as secondary objectives in case multiple min-sum paths exist between s and t. From these variants, only the widest min-sum link-disjoint paths problem is not NP-hard.Li et al. [112] studied the min-sum disjoint paths problem, where the link-weight functions are different for the primary and backup paths and showed that this problem is hard to approximate. Bhatia [117] demonstrated that the problem remains hard to approximate in the case that the weights for the links of the backup path are a fraction 0<ρ<1 of the normal link weights (for the primary path).Sherali et al. [118] investigated the time-dependent min-sum disjoint paths problem, where the link weights are time-dependent. They proved that the problem is NP-hard, even if only one link is time-dependent and all other links are static.


### 4.1. Min-Sum Disjoint Paths

Finding min-sum disjoint paths is equivalent to finding a minimum-cost flow in unit-capacity networks [26]: a minimum-cost flow of k will traverse k disjoint paths. In fact, Suurballe's algorithm, which is most often cited as an algorithm to compute two disjoint paths, is an algorithm that uses augmenting paths, like in several max-flow algorithms. The original Suurballe algorithm as presented in [119] allows to compute k node (or link) disjoint paths between a single source-destination pair, by using k shortest path computations. Later, this approach was used by Suurballe and Tarjan [120] to find two link (or node) disjoint paths from a source s to all other nodes in the network (i.e., N-1 source-destination pairs), by using only two shortest-paths computations, that is, in O(NlogN+L) time. Both papers focus on directed networks, but can also be applied to undirected networks.In directed networks, a link-disjoint paths algorithm can be used to compute node-disjoint paths, if we split each nodeu into two nodes u1 and u2, with a directed link (u1,u2), and the incoming links of u connected to u1 and the outgoing links of u departing from u2.In undirected networks, a link-disjoint paths algorithm can be used to compute node-disjoint paths by the transformation described in Section2.2.We will present the Suurballe-Tarjan algorithm, see Algorithm10, for computing two link-disjoint paths between s and every other node in the network.Algorithm 10:Suurballe-Tarjan-2-link-disjoint-paths (G,s).
(
1
) Compute the shortest paths tree T rooted at s
(2) Modify the weights of each link(u,v)∈ℒ to w′(u,v)=w(u,v)-l(s,v)+l(s,u)
/*l(s,i) is the length of the shortest path in G from s to i*/
(3) Fori=1,…,N
(4)l(i)←∞, q(i)←NIL, π(i)←NIL
(5)l(s)←0
(6)Q←𝒩
(7) WhileQ≠∅
(8)EXTRACT-MIN (Q)→u
(9)DELETE (T,u) /*T becomes a forest of subtrees*/
(10)  For each non-tree link (i,j) in T such that i=u or i and j are in different subtrees
(11)      Ifl(u)+w(i,j)<l(j)
(12)  l(j)←l(u)+w(i,j),  π(j)←i,q(j)←uInstead of finding an augmenting path for each source-destination pair, Suurballe and Tarjan have found a way to combine these augmenting flow computations into two Dijkstra-like shortest-paths computations. First a shortest paths treeT is computed in line 1, and based on the computed shortest path lengths, the link weights are modified in line 2. This link weight modification was also used by Suurballe and is to assure that w(u,v)≥0 for all links, with equality if (u,v) is in T. In Suurballe's original algorithm the direction of the links on the shortest path from s to d was reversed, after which a shortest (augmenting) path in the newly modified graph was computed. In Suurballe-Tarjan's algorithm the links maintain their direction, but an additional parameter q is used instead. The algorithm proceeds in a Dijkstra-like fashion. Lines 3–6 correspond to the initialization of the smallest length l(i) from s to i found so far, its corresponding predecessor list π(i) and q(i). The algorithm repeatedly extracts a node of minimum length (in line 8) and removes that node from the tree T (in line 9). A slightly different relaxation procedure is used (lines 10–12). Upon termination of the algorithm, the disjoint paths between the source s and a destination t can be retrieved via the lists π() and q() with Algorithm 11.Algorithm 11:Return-Suurballe-Tarjan-2-link-disjoint-paths (G,s,t).
(
1
)  x←t
(2) Whilex≠s
(3)mark x
(4)x←q(x)
(5) Fori=1,2
(6)x←t
(7) Whilex≠s
(8)If x is marked
(9)       unmarkx
(10)Pi←Pi+(p(x),x)
(11)x←p(x)
(10)   Else
(11)Pi←Pi+(y,x) /*y is parent of x in T*/
(12)x←yTaft-Plotkin et al. [121] extended the approach of Suurballe and Tarjan in two ways: (1) they return maximally disjoint paths, and (2) they also take bandwidth into account. Their algorithm, called MADSWIP, computes maximum-bandwidth maximally disjoint paths and minimizes the total weight as a secondary objective. Consequently, by assigning all links equal bandwidth, the MADSWIP algorithm returns the min-sum maximally disjoint paths.For a distributed disjoint paths algorithm, we refer to the work of Ogier et al. [122] and Sidhu et al. [123].Roskind and Tarjan [124] presented an O(LlogL+k2N2) algorithm for finding k link-disjoint spanning trees of minimum total weight. Xue et al. [125, 126] have considered quality of service and quality of protection issues in computing two disjoint trees (quality of Protection (QoP) as used by Xue et al. refers to the amount of link failures that can be survived. QoP sometimes is used to refer to probabilistic survivability, as discussed in the following section or protection differentiation as overviewed by Cholda et al. [127]). Ramasubramanian et al. [128] proposed a distributed algorithm for computing two disjoint trees. Guo et al. [129] considered finding two link-disjoint paths subject to multiple Quality-of-Service constraints.


### 4.2. Probabilistic Survivability

When two disjoint primary and backup paths are reserved for a connection, any failure on the primary path can be survived by using the backup path. The backup path therefore provides 100% survivability guarantee against a single failure. When no backup paths are available, that is, unprotected paths are used, then the communication along a path will fail if there is a failure on that path. Banner and Orda [130] have introduced the term p-survivable connection to denote a connection for which there is a probability ≥p that all its links are operational (the related notion of Quality of Protection (QoP), as defined by Gerstel and Sasaki [131], was argued to be difficult to apply to general networks). The previous two cases correspond to p=1 and p=0, respectively. Banner and Orda proved that, under the single-link failure model, at most two paths are needed to establish a p-survivable connection, if it exists. Based on this observation, they studied and proposed algorithms for several problem variants, namely establishing p-survivable-B-bandwidth, most survivable,  and widest p-survivable connections for 1 : 1 and 1+1 protection architectures (the MADSWIP algorithm [121] can also be used to find the most survivable connection). The p-survivable-B-bandwidth problem asks for a connection with survivability ≥p and bandwidth ≥B and solving it provides a foundation for solving the other problems. We will therefore  discuss the solution proposed by Banner and Orda for the p-survivable-B-bandwidth problem.The approach by Banner and Orda to solve thep-survivable-B-bandwidth problem is twofold. First, the graph is transformed, after which a minimum-cost flow is found on the resulting graph. The graph transformation is depicted in Figure 2 and slightly differs for the 1 : 1 and 1+1 cases. Clearly, if a link does not have sufficient spare capacity to accommodate the requested bandwidth B, then it does not need to be considered further (Figure 2(a)). If, for 1 : 1 protection, be≥B, then there is sufficient bandwidth for both disjoint paths, since the backup path is only used after failure of the primary path. To allow for both paths to share that link, it is transformed to two links (Figure 2(b)). If the original link is only used by one path, then that link is protected, and hence the weight 0 is assigned to the top link. If both paths have to use the original link, then the connection's survivability is affected by the failure probability of that link, which is why the weight -ln(1-pe) is assigned to the lower link (the logarithm is used to transform a multiplicative metric to an additive metric). The same applies to the 1+1 case, with the exception that the concurrent transmission of data over both paths requires twice the requested bandwidth. For the remaining range B≤be<2B for 1+1 protection (Figure 2(c)), it holds that only one of the paths can use that link, which is why there is no weight penalty.Graph transformation for thep-survivable-B-bandwidth problem. For each link e with capacity be and failure probability pe, the new links consist of a bandwidth-weight pair.
(a)
(b)
(c)In the transformed graph, a minimum-cost flow of2B units corresponds to two maximally disjoint paths of each B bandwidth. The minimum-cost flow could, for instance, be found with the cycle-canceling algorithm of Goldberg and Tarjan [132], while the corresponding maximally disjoint paths could be returned via a flow-decomposition algorithm [26].Luo et al. [133] studied the min-sum p-survivable connection problem, where each link is characterized by a weight and a failure probability, and the problem is to find a connection of least weight and survivability ≥p. Contrary to the min-sum maximally-disjoint paths problem, this problem is NP-hard, since it contains the NP-hard restricted shortest paths problem (e.g., see [134]). Luo et al. proposed an ILP and two approximation algorithms for this problem. Chakrabarti and Manimaran [135] studied the min-sum p-survivable-B-bandwidth problem, for which they considered a segment-based protection strategy.She et al. [114] have considered the problem of finding two link-disjoint paths, for which the probability that at least one of these paths will not fail is maximized. They refer to this problem as the maximum-reliability (max-rel) link-disjoint paths problem. The rationale behind this problem is to establish two disjoint paths that give 100% protection against a single-link failure, while reducing the failure probability of the connection as much as possible when multiple failures may occur. Assuming that the link-failure probabilities pi are independent, then the reliability of a connection (consisting of two link-disjoint paths P1 and P2) is defined as ∏i∈P1qi+∏j∈P2qj+∏i∈P1qi·∏j∈P2qj, with qi=1-pi, for i∈ℒ. The max-rel link-disjoint paths problem is proven to be NP-complete. She et al. [114] evaluated two simple heuristic algorithms that both transform the link probabilities pi to link weights logqqi, with qi=1-pi, for i∈ℒ, and 0<q<1. Based on these weights, one heuristic finds a shortest path, prunes its links from the graphs, and finds a shortest path in the pruned graph. This is often referred to as an active-path-first (APF) approach. The second heuristic uses Suurballe's algorithm to find two link-disjoint paths. Contrary to the first heuristic, the second always returns link-disjoint paths if they exist.


### 4.3. Multiple Failures

The single-link failure model has been most often considered in the literature, but multiple failures may occur as follows.(i)
Due to lengthy repair times of network equipment, there is a fairly long time span in which new failures could occur.(ii)
In case of terrorist attacks, several targeted parts of the network could be damaged. With Suurballe's algorithm,k link/node-disjoint paths can be found to establish full protection against k-1 link/node failures.(iii)
In layered networks, for instance IP-over-WDM, one failure on the lowest-layer network, may cause multiple failures on higher-layer networks. Similarly, the links of a (single-layered) network may share the same duct, in which case a damaging of the duct may damage all the links inside. These links are often said to belong to the same shared risk link group (SRLG) (the node variant SRNG also exists. When both nodes and links can belong to a shared risk group, the term Shared Risk Resource Group (SRRG) is used, e.g., see [136]). Finding two SRLG-disjoint paths—paths of which the links in one path may not share a risk link group with links from the other path—is an NP-complete problem [137]. In specific cases, the SRLG-disjoint paths problem is polynomially solvable, as discussed by Bhandari [138], Datta and Somani [139], and Luo and Wang [140]. In those cases, for instance, when the links in a SRLG share the same endpoint, a graph transformation can be made that reflects the shared risk groups, and on which a simple link-disjoint paths algorithm can be run. Lee et al. [141] have generalized the SRLG problem to include failure probabilities. In the deterministic SRLG scenario, when a SRLG r fails (e.g., a cable in the physical network is cut) all higher-layer links that belong to that group fail. In the probabilistic SRLG (PSRLG) scenario, the links (i,j) in that PSRLG r fail with probability pijr>0. If pijr∈{0,1}, for (i,j)∈ℒ, then the problem of finding PSRLG-disjoint paths reduces to the NP-complete problem of finding SRLG-disjoint paths. For SRLG types of problems, often an integer programming formulation is provided (e.g., [137, 142–144]) or an active-path-first (APF) approach is used as a heuristic. Hu [137] provided a basic ILP formulation to return a min-sum pair of SRLG-disjoint paths. Xu et al. [143] gave an ILP and an APF heuristic for the case of shared (backup paths) protection.(iv)
Natural disasters may affect all nodes and links within a certain geographical area. Work on multilink geographic failures has mostly focused on determining the geographic max-flow and min-cut values of a network under geographic failures of circular shape (e.g., Sen et al. [145], Agarwal et al. [146], and Neumayer et al. [147]). Trajanovski et al. [148] proved that, the problem of finding two region-disjoint paths is NP-hard, and they proposed a heuristic for it.


## 4.1. Min-Sum Disjoint Paths

Finding min-sum disjoint paths is equivalent to finding a minimum-cost flow in unit-capacity networks [26]: a minimum-cost flow of k will traverse k disjoint paths. In fact, Suurballe's algorithm, which is most often cited as an algorithm to compute two disjoint paths, is an algorithm that uses augmenting paths, like in several max-flow algorithms. The original Suurballe algorithm as presented in [119] allows to compute k node (or link) disjoint paths between a single source-destination pair, by using k shortest path computations. Later, this approach was used by Suurballe and Tarjan [120] to find two link (or node) disjoint paths from a source s to all other nodes in the network (i.e., N-1 source-destination pairs), by using only two shortest-paths computations, that is, in O(NlogN+L) time. Both papers focus on directed networks, but can also be applied to undirected networks.In directed networks, a link-disjoint paths algorithm can be used to compute node-disjoint paths, if we split each nodeu into two nodes u1 and u2, with a directed link (u1,u2), and the incoming links of u connected to u1 and the outgoing links of u departing from u2.In undirected networks, a link-disjoint paths algorithm can be used to compute node-disjoint paths by the transformation described in Section2.2.We will present the Suurballe-Tarjan algorithm, see Algorithm10, for computing two link-disjoint paths between s and every other node in the network.Algorithm 10:Suurballe-Tarjan-2-link-disjoint-paths (G,s).
(
1
) Compute the shortest paths tree T rooted at s
(2) Modify the weights of each link(u,v)∈ℒ to w′(u,v)=w(u,v)-l(s,v)+l(s,u)
/*l(s,i) is the length of the shortest path in G from s to i*/
(3) Fori=1,…,N
(4)l(i)←∞, q(i)←NIL, π(i)←NIL
(5)l(s)←0
(6)Q←𝒩
(7) WhileQ≠∅
(8)EXTRACT-MIN (Q)→u
(9)DELETE (T,u) /*T becomes a forest of subtrees*/
(10)  For each non-tree link (i,j) in T such that i=u or i and j are in different subtrees
(11)      Ifl(u)+w(i,j)<l(j)
(12)  l(j)←l(u)+w(i,j),  π(j)←i,q(j)←uInstead of finding an augmenting path for each source-destination pair, Suurballe and Tarjan have found a way to combine these augmenting flow computations into two Dijkstra-like shortest-paths computations. First a shortest paths treeT is computed in line 1, and based on the computed shortest path lengths, the link weights are modified in line 2. This link weight modification was also used by Suurballe and is to assure that w(u,v)≥0 for all links, with equality if (u,v) is in T. In Suurballe's original algorithm the direction of the links on the shortest path from s to d was reversed, after which a shortest (augmenting) path in the newly modified graph was computed. In Suurballe-Tarjan's algorithm the links maintain their direction, but an additional parameter q is used instead. The algorithm proceeds in a Dijkstra-like fashion. Lines 3–6 correspond to the initialization of the smallest length l(i) from s to i found so far, its corresponding predecessor list π(i) and q(i). The algorithm repeatedly extracts a node of minimum length (in line 8) and removes that node from the tree T (in line 9). A slightly different relaxation procedure is used (lines 10–12). Upon termination of the algorithm, the disjoint paths between the source s and a destination t can be retrieved via the lists π() and q() with Algorithm 11.Algorithm 11:Return-Suurballe-Tarjan-2-link-disjoint-paths (G,s,t).
(
1
)  x←t
(2) Whilex≠s
(3)mark x
(4)x←q(x)
(5) Fori=1,2
(6)x←t
(7) Whilex≠s
(8)If x is marked
(9)       unmarkx
(10)Pi←Pi+(p(x),x)
(11)x←p(x)
(10)   Else
(11)Pi←Pi+(y,x) /*y is parent of x in T*/
(12)x←yTaft-Plotkin et al. [121] extended the approach of Suurballe and Tarjan in two ways: (1) they return maximally disjoint paths, and (2) they also take bandwidth into account. Their algorithm, called MADSWIP, computes maximum-bandwidth maximally disjoint paths and minimizes the total weight as a secondary objective. Consequently, by assigning all links equal bandwidth, the MADSWIP algorithm returns the min-sum maximally disjoint paths.For a distributed disjoint paths algorithm, we refer to the work of Ogier et al. [122] and Sidhu et al. [123].Roskind and Tarjan [124] presented an O(LlogL+k2N2) algorithm for finding k link-disjoint spanning trees of minimum total weight. Xue et al. [125, 126] have considered quality of service and quality of protection issues in computing two disjoint trees (quality of Protection (QoP) as used by Xue et al. refers to the amount of link failures that can be survived. QoP sometimes is used to refer to probabilistic survivability, as discussed in the following section or protection differentiation as overviewed by Cholda et al. [127]). Ramasubramanian et al. [128] proposed a distributed algorithm for computing two disjoint trees. Guo et al. [129] considered finding two link-disjoint paths subject to multiple Quality-of-Service constraints.


## 4.2. Probabilistic Survivability

When two disjoint primary and backup paths are reserved for a connection, any failure on the primary path can be survived by using the backup path. The backup path therefore provides 100% survivability guarantee against a single failure. When no backup paths are available, that is, unprotected paths are used, then the communication along a path will fail if there is a failure on that path. Banner and Orda [130] have introduced the term p-survivable connection to denote a connection for which there is a probability ≥p that all its links are operational (the related notion of Quality of Protection (QoP), as defined by Gerstel and Sasaki [131], was argued to be difficult to apply to general networks). The previous two cases correspond to p=1 and p=0, respectively. Banner and Orda proved that, under the single-link failure model, at most two paths are needed to establish a p-survivable connection, if it exists. Based on this observation, they studied and proposed algorithms for several problem variants, namely establishing p-survivable-B-bandwidth, most survivable,  and widest p-survivable connections for 1 : 1 and 1+1 protection architectures (the MADSWIP algorithm [121] can also be used to find the most survivable connection). The p-survivable-B-bandwidth problem asks for a connection with survivability ≥p and bandwidth ≥B and solving it provides a foundation for solving the other problems. We will therefore  discuss the solution proposed by Banner and Orda for the p-survivable-B-bandwidth problem.The approach by Banner and Orda to solve thep-survivable-B-bandwidth problem is twofold. First, the graph is transformed, after which a minimum-cost flow is found on the resulting graph. The graph transformation is depicted in Figure 2 and slightly differs for the 1 : 1 and 1+1 cases. Clearly, if a link does not have sufficient spare capacity to accommodate the requested bandwidth B, then it does not need to be considered further (Figure 2(a)). If, for 1 : 1 protection, be≥B, then there is sufficient bandwidth for both disjoint paths, since the backup path is only used after failure of the primary path. To allow for both paths to share that link, it is transformed to two links (Figure 2(b)). If the original link is only used by one path, then that link is protected, and hence the weight 0 is assigned to the top link. If both paths have to use the original link, then the connection's survivability is affected by the failure probability of that link, which is why the weight -ln(1-pe) is assigned to the lower link (the logarithm is used to transform a multiplicative metric to an additive metric). The same applies to the 1+1 case, with the exception that the concurrent transmission of data over both paths requires twice the requested bandwidth. For the remaining range B≤be<2B for 1+1 protection (Figure 2(c)), it holds that only one of the paths can use that link, which is why there is no weight penalty.Graph transformation for thep-survivable-B-bandwidth problem. For each link e with capacity be and failure probability pe, the new links consist of a bandwidth-weight pair.
(a)
(b)
(c)In the transformed graph, a minimum-cost flow of2B units corresponds to two maximally disjoint paths of each B bandwidth. The minimum-cost flow could, for instance, be found with the cycle-canceling algorithm of Goldberg and Tarjan [132], while the corresponding maximally disjoint paths could be returned via a flow-decomposition algorithm [26].Luo et al. [133] studied the min-sum p-survivable connection problem, where each link is characterized by a weight and a failure probability, and the problem is to find a connection of least weight and survivability ≥p. Contrary to the min-sum maximally-disjoint paths problem, this problem is NP-hard, since it contains the NP-hard restricted shortest paths problem (e.g., see [134]). Luo et al. proposed an ILP and two approximation algorithms for this problem. Chakrabarti and Manimaran [135] studied the min-sum p-survivable-B-bandwidth problem, for which they considered a segment-based protection strategy.She et al. [114] have considered the problem of finding two link-disjoint paths, for which the probability that at least one of these paths will not fail is maximized. They refer to this problem as the maximum-reliability (max-rel) link-disjoint paths problem. The rationale behind this problem is to establish two disjoint paths that give 100% protection against a single-link failure, while reducing the failure probability of the connection as much as possible when multiple failures may occur. Assuming that the link-failure probabilities pi are independent, then the reliability of a connection (consisting of two link-disjoint paths P1 and P2) is defined as ∏i∈P1qi+∏j∈P2qj+∏i∈P1qi·∏j∈P2qj, with qi=1-pi, for i∈ℒ. The max-rel link-disjoint paths problem is proven to be NP-complete. She et al. [114] evaluated two simple heuristic algorithms that both transform the link probabilities pi to link weights logqqi, with qi=1-pi, for i∈ℒ, and 0<q<1. Based on these weights, one heuristic finds a shortest path, prunes its links from the graphs, and finds a shortest path in the pruned graph. This is often referred to as an active-path-first (APF) approach. The second heuristic uses Suurballe's algorithm to find two link-disjoint paths. Contrary to the first heuristic, the second always returns link-disjoint paths if they exist.


## 4.3. Multiple Failures

The single-link failure model has been most often considered in the literature, but multiple failures may occur as follows.(i)
Due to lengthy repair times of network equipment, there is a fairly long time span in which new failures could occur.(ii)
In case of terrorist attacks, several targeted parts of the network could be damaged. With Suurballe's algorithm,k link/node-disjoint paths can be found to establish full protection against k-1 link/node failures.(iii)
In layered networks, for instance IP-over-WDM, one failure on the lowest-layer network, may cause multiple failures on higher-layer networks. Similarly, the links of a (single-layered) network may share the same duct, in which case a damaging of the duct may damage all the links inside. These links are often said to belong to the same shared risk link group (SRLG) (the node variant SRNG also exists. When both nodes and links can belong to a shared risk group, the term Shared Risk Resource Group (SRRG) is used, e.g., see [136]). Finding two SRLG-disjoint paths—paths of which the links in one path may not share a risk link group with links from the other path—is an NP-complete problem [137]. In specific cases, the SRLG-disjoint paths problem is polynomially solvable, as discussed by Bhandari [138], Datta and Somani [139], and Luo and Wang [140]. In those cases, for instance, when the links in a SRLG share the same endpoint, a graph transformation can be made that reflects the shared risk groups, and on which a simple link-disjoint paths algorithm can be run. Lee et al. [141] have generalized the SRLG problem to include failure probabilities. In the deterministic SRLG scenario, when a SRLG r fails (e.g., a cable in the physical network is cut) all higher-layer links that belong to that group fail. In the probabilistic SRLG (PSRLG) scenario, the links (i,j) in that PSRLG r fail with probability pijr>0. If pijr∈{0,1}, for (i,j)∈ℒ, then the problem of finding PSRLG-disjoint paths reduces to the NP-complete problem of finding SRLG-disjoint paths. For SRLG types of problems, often an integer programming formulation is provided (e.g., [137, 142–144]) or an active-path-first (APF) approach is used as a heuristic. Hu [137] provided a basic ILP formulation to return a min-sum pair of SRLG-disjoint paths. Xu et al. [143] gave an ILP and an APF heuristic for the case of shared (backup paths) protection.(iv)
Natural disasters may affect all nodes and links within a certain geographical area. Work on multilink geographic failures has mostly focused on determining the geographic max-flow and min-cut values of a network under geographic failures of circular shape (e.g., Sen et al. [145], Agarwal et al. [146], and Neumayer et al. [147]). Trajanovski et al. [148] proved that, the problem of finding two region-disjoint paths is NP-hard, and they proposed a heuristic for it.


## 5. Conclusion

We have provided an overview of algorithms for network survivability. We have considered how to verify that a network has certain connectivity properties, how to augment an existing network to reach a given connectivity, and, lastly, how to find alternative paths in case network failures occur. Our focus has been on algorithms for general networks, although much work has also been done for specific networks, such as optical networks, where additional constraints like wavelength continuity and signal impairments induce an increased complexity, for example, see our work [149–151]. We have not discussed how to design a survivable network from scratch. Typically network design problems are hard to solve and involve many constraints, but since they only need to be solved sporadically, longer computation times are permitted. Predominantly, integer programming is used to design a network, as we have done in [152].



---

*Source: 932456-2012-12-05.xml*