An Approximation Algorithm for the Minimum-Cost <i>k</i>-Vertex Connected Subgraph

Abstract

We present an approximation algorithm for the problem of finding a minimum-cost k-vertex connected spanning subgraph, assuming that the number of vertices is at least 6k2 . The approximation guarantee is six times the kth harmonic number (which is O(log k)), and this is also an upper bound on the integrality ratio for a standard linear programming relaxation.