Keywords and Synonyms

Highly connected subgraphs; Sparse certificates

Problem Definition

An undirected graph is said to be k-connected (specifically, k-vertex‐connected) if the removal of any set of \( { k-1 } \) or fewer vertices (with their incident edges) does not disconnect G. Analogously, it is k-edge‐connected if the removal of any set of \( { k-1 } \) edges does not disconnect G. Menger's theorem states that a k-vertex‐connected graph has at least k openly vertex‐disjoint paths connecting every pair of vertices. For k-edge‐connected graphs there are k edge-disjoint paths connecting every pair of vertices. The connectivity of a graph is the largest value of k for which it is k-connected. Finding the connectivity of a graph, and finding k disjoint paths between a given pair of vertices can be found using algorithms for maximum flow. An edge is said to be critical in a k-connected graph if upon its removal the graph is no longer k-connected.

The problem of finding a minimum‐cardinality k-vertex‐connected (k-edge‐connected) subgraph that spans all vertices of a given graph is called k-VCSS (k-ECSS) and is known to be nondeterministic polynomial-time hard for \( { k\ge 2 } \). We review some results in finding approximately minimum solutions to k-VCSS and k-ECSS. We focus primarily on simple graphs. A simple approximation algorithm is one that considers the edges in some order and removes edges that are not critical. It thus outputs a k‑connected subgraph in which all edges are critical and it can be shown that it is a 2‑approximation algorithm (that outputs a solution with at most kn edges in an n-vertex graph, and since each vertex has to have degree at least k, we can claim that \( { kn/2 } \) edges are necessary).

Approximation algorithms that do better than the simple algorithm mentioned above can be classified into two categories: depth first search (DFS) based, and matching based.

Key Results

Lower Bounds for k-Connected Spanning Subgraphs

Each node of a k-connected graph has at least k edges incident to it. Therefore, the sum of the degrees of all its nodes is at least kn, where n is the number of its nodes. Since each edge is counted twice in this degree-sum, the cardinality of its edges is at least \( { kn/2 } \). This is called the degree lower bound. Expanding on this idea yields a stronger lower bound on the cardinality of a k-connected spanning subgraph of a given graph. Let D k be a subgraph in which the degree of each node is at least k. Unlike a k-connected subgraph, D k has no connectivity constraints. The counting argument above shows that any D k has at least \( { kn/2 } \) edges. A minimum cardinality D k can be computed in polynomial time by reducing the problem to matching, and it is called the matching lower bound.

DFS-Based Approaches

The following natural algorithm finds a 3/2 approximation for 2-ECSS. Root the tree at some node r and run DFS. All edges of the graph are now either tree edges or back edges. Process the DFS tree in postorder. For each subtree, if the removal of the edge from its root to its parent separates the graph into two components, then add a farthest-back edge from this subtree, whose other end is closest to r. It can be shown that the number of back edges added by the algorithm is at most half the size of Opt.

This algorithm has been generalized to solve the 2‑VCSS problem with the same approximation ratio, by adding carefully chosen back edges that allow the deletion of tree edges. Wherever it is unable to delete a tree edge, it adds a vertex to an independent set I. In the final analysis, the number of edges used is less than \( { n+|I| } \). Since Opt is at least \( { \max(n,2|I|) } \), it obtains a 3/2‑approximation ratio.

The algorithm can also be extended to the k-ECSS problem by repeating these ideas \( { k/2 } \) times, augmenting the connectivity by 2 in each round. It has been shown that this algorithm achieves a performance of about 1.61.

Matching-Based Approaches

Several approximation algorithms for k-ECSS and k-VCSS problems have used a minimum cardinality D k as a starting solution, which is then augmented with additional edges to satisfy the connectivity constraints. This approach yields better ratios than the DFS-based approaches.

\( { 1+\frac{1}{k} } \) Algorithm for k-VCSS

Find a minimum cardinality \( { D_{k-1} } \). Add just enough additional edges to it to make the subgraph k-connected. In this step, it is ensured that the edges added are critical. It is known by a theorem of Mader that in a k-connected graph, a cycle of critical edges contains at least one node of degree k. Since the edges added by the algorithm in the second step are all critical, there can be no cycle induced by these edges because the degree of all the nodes on such a cycle would be at least \( { k+1 } \). Therefore, at most \( { n-1 } \) edges are added in this step. The number of edges added in the first step, in the minimum \( { D_{k-1} } \) is at most \( { Opt-n/2 } \). The total number of edges in the solution thus computed is at most \( { (1+1/k) } \) times the number of edges in an optimal k-VCSS.

\( { 1+\frac{2}{k+1} } \) Algorithm for k-ECSS

Mader's theorem about cycles induced by critical edges is valid only for vertex connectivity and not edge connectivity, Therefore, a different algorithm is proposed for k-ECSS in graphs that are k‑edge‐connected, but not k-connected. This algorithm finds a minimum cardinality D k and augments it with a minimal set of edges to make the subgraph k-edge‐connected. The number of edges added in the last step is at most \( { \frac{k}{k+1}(n-1) } \). Since the number of edges added in the first step is at most Opt, the total number of edges is at most \( { (1+\frac{2}{k+1})Opt } \).

Better Algorithms for Small k

For \( { k\in\{2,3\} } \), better algorithms have been obtained by implementing the abovementioned algorithms carefully, deleting unnecessary edges, and by getting better lower bounds. For \( { k=2 } \), a 4/3 approximation can be obtained by generating a path/cycle cover from a minimum cardinality D 2 and 2‑connecting them one at a time to a “core” component. Small cycles/paths allow an edge to be deleted when they are 2‑connected to the core, which allows a simple amortized analysis. This method also generalizes to the 3-ECSS problem, yielding a 4/3 ratio.

Hybrid approaches have been proposed which use the path/cycle cover to generate a specific DFS tree of the original graph and then 2‑connect the tree, trying to delete edges wherever possible. The best ratios achieved using this approach are 5/4 for 2-ECSS, 9/7 for 2‑VCSS, and 5/4 for 2‑VCSS in 3‑connected graphs.

Applications

Network design is one of the main application areas for this work. This involves the construction of low-cost highly connected networks.

Recommended Reading

For additional information on DFS, matchings and path/cycle covers, see [3]. Fast 2‑approximation algorithms for k-ECSS and k-VCSS were studied by Nagamochi and Ibaraki [13]. DFS-based algorithms for 2‑connectivity were introduced by Khuller and Vishkin [11]. They obtained 3/2 for 2-ECSS, 5/3 for 2‑VCSS, and 2 for weighted k-ECSS. The ratio for 2‑VCSS was improved to 3/2 by Garg et al.  [6], 4/3 by Vempala and Vetta [14], and 9/7 by Gubbala and Raghavachari [7]. Khuller and Raghavachari [10] gave an algorithm for k-ECSS, which was later improved by Gabow [4], who showed that the algorithm obtains a ratio of about 1.61. Cheriyan et al. [2] studied the k-VCSS problem with edge weights and designed an \( { O(\log{k}) } \) approximation algorithm in graphs with at least 6k 2 vertices.

The matching-based algorithms were introduced by Cheriyan and Thurimella [1]. They proposed algorithms with ratios of \( { 1+\frac{1}{k} } \) for k-VCSS, \( { 1+\frac{2}{k+1} } \) for k-ECSS, \( { 1+\frac{1}{k} } \) for k-VCSS in directed graphs, and \( { 1+\frac{4}{\sqrt{k}} } \) for k-ECSS in directed graphs. Vempala and Vetta [14] obtained a ratio of 4/3 for 2‑VCSS. The ratios were further improved by Krysta and Kumar [12], who introduced the hybrid approach, which was used to derive a 5/4 algorithm by Jothi et al. [9]. A 3/2‑approximation algorithm for 3-ECSS has been proposed by Gabow [5] that works on multigraphs, whereas the earlier algorithm of Cheriyan and Thurimella gets the same ratio in simple graphs only. This ratio has been improved to 4/3 by Gubbala and Raghavachari [8].