A 3-Approximation Algorithm for Finding Optimum 4,5-Vertex-Connected Spanning Subgraphs

The problem of finding a minimum weight k-vertex connected spanning subgraph in a graph G = (V, E) is considered. For k ≥ 2, this problem is known to be NP-hard. Based on the paper of Auletta, Dinitz, Nutov, and Parente in this issue, we derive a 3-approximation algorithm for k ∈ {4,5}. This improves the best previously known approximation ratios 41/6 and 417/30, respectively. The complexity of the suggested algorithm is O(|V|⁵) for the deterministic and O(\V\⁴log|V|) for the randomized version. The way of solution is as follows. Analyzing a subgraph constructed by the algorithm of the aforementioned paper, we prove that all its "small" cuts have exactly two sides and separate a certain fixed pair of vertices. Such a subgraph is augmented to a k-connected one (optimally) by at most four executions of a min-cost k-flow algorithm.