Approximation algorithms for minimum-cost k-vertex connected subgraphs

(MATH) We present two new algorithms for the problem of finding a minimum-cost k -vertex connected spanning subgraph. The first algorithm works on undirected graphs with at least 6k 2 vertices and achieves an approximation factor of 6 times the k th harmonic number, which is $O(\log k)$. The second algorithm works on directed and undirected graphs. It gives an $O(\sqrt{ n /\keps})$-approximation algorithm for any $\keps > 0$ and $k \le (1-\keps)n$. The latter algorithm also extends to other problems in network design with vertex connectivity requirements. Our main tools are setpair relaxations, a theorem of Mader's (in the undirected case) and iterative rounding (general case).

Authors

• Joseph Cheriyan
• Santosh S. Vempala
• Adrian Vetta

Keywords

No keywords are indexed for this paper.