A 2-approximation algorithm for finding an optimum 3-vertex-connected spanning subgraph

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. Combining properties of inclusion-minima l k-vertex connected graphs and of k-out-connected graphs (i.e., graphs whi ch contain a vertex from which there exist k internally vertex-disjoint pat hs to every other vertex), we derive polynomial time algorithm for finding a ([k/2] + 1)-connected subgraph with a weight at most twice the optimum to the original problem. In particular, we obtain a 2-approximation algorithm for the case k = 3 of our problem. This improves the best previously known approximation ratio 3. The complexity of the algorithm is O(/V/(3)/E/) = O (/V/(5)). (C) 1999 Academic Press.