An improved approximation algorithm for the minimum-cost subset k-connected subgraph problem
Bundit Laekhanukit · arXiv (Cornell University) · 2011
The minimum-cost subset $k$-connected subgraph problem is a cornerstone problem in the area of network design with vertex connectivity requirements. In this problem, we are given a graph $G=(V,E)$ with costs on edges and a set of terminals $T$. The goal is to find a minimum cost subgraph such that every pair of terminals are connected by $k$ openly (vertex) disjoint paths. In this paper, we present an approximation algorithm for the subset $k$-connected subgraph problem which improves on the previous best approximation guarantee of $O(k^2\log{k})$ by Nutov (FOCS 2009). Our approximation guarantee, $α(|T|)$, depends upon the number of terminals: [α(|T|) \ \ =\ \ O(|T|^2) & if |T| k$. This suggests that the hardest instances of the problem are when $|T|\approx k$.