Approximating Minimum-Cost k-Node Connected Subgraphs via Independence-Free Graphs

Joseph Cheriyan, Laszlo A. Vegh

We present a 6-approximation algorithm for the minimum-cost $k$-node connected spanning subgraph problem, assuming that the number of nodes is at least $k^3(k-1)+k$. We apply a com…