Approximating k-node Connected Subgraphs via Critical Graphs

We present two new approximation algorithms for the problem of finding a k-node connected spanning subgraph (directed or undirected) of minimum cost. The best known approximation guarantees for this problem were $O(\min \{k,\frac{n}{\sqrt{n-k}}\})$ for both directed and undirected graphs, and $O(\ln k)$ for undirected graphs with $n \geq 6k^2$, where $n$ is the number of nodes in the input graph. Our first algorithm has approximation ratio $O(\frac{n}{n-k}\ln^2 k)$, which is $O(\ln^2 k)$ except for very large values of $k$, namely, $k=n-o(n)$. This algorithm is based on a new result on $\ell$-connected $p$-critical graphs, which is of independent interest in the context of graph theory. Our second algorithm uses the primal-dual method and has approximation ratio $O(\sqrt{n} \ln k)$ for all values of $n,k$. Combining these two gives an algorithm with approximation ratio $O(\ln k \cdot \min \{\sqrt{k},\frac{n}{n-k} \ln k\})$, which asymptotically improves the best known approximation guarantee for directed graphs for all values of $n,k$, and for undirected graphs for $k>\sqrt{n/6}$. Moreover, this is the first algorithm that has an approximation guarantee better than $\Theta(k)$ for all values of $n,k$. Our approximation ratio also provides an upper bound on the integrality gap of the standard LP-relaxation.