A 3-approximation algorithm for finding optimum 4,5-vertex-connected spanning subgraphs

The problem of finding a minimum weight k-vertex connected spanning subgrap h in a graph G = (V, E) is considered. For k greater than or equal to 2, th is problem is known to be NP-hard. Based on the paper of Auletta, Dinitz, N utov, and Parente in this issue, we derive a 3-approximation algorithm for k is an element of {4, 5}. This: improves the best previously known approxi mation ratios 41/6 and 417/30, respectively. The complexity of the suggeste d algorithm is O(/V/(5)) for the deterministic and O(/V/(4)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 al l 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. (C) 1999 Academ ic Press.