Finding optimum k-vertex connected spanning subgraphs: Improved approximation algorithms for k=3, 4, 5

The problem of finding a minimum weight k-vertex connected spanning subgraph is considered. For k>1, this problem is known to be NP-hard. Combining properties of inclusion-minimal k-vertex connected graphs and of k-out-connected graphs (i.e., graphs which contain a vertex from which there are k internally vertex-disjoint paths to every other vertex), we derive polynomial time approximation algorithms for several values of k. (i) For k=3, we give an algorithm with approximation factor 2. This improves the best previously known factor 3. (ii) For k= 4 and k= 5, we give an algorithm with approximation factor 3.