Published: August 17, 2012
Abstract: [Plain Text Version]
In the Survivable Network Design Problem (SNDP), we are given an undirected graph $G(V,E)$ with costs on edges, along with an integer connectivity requirement $r(u,v)$ for each pair $u, v$ of vertices. The goal is to find a minimum-cost subset $E^*$ of edges such that in the subgraph of $G$ induced by $E^*$, each pair $u, v$ of vertices is $r(u,v)$-connected. In the edge-connectivity version, a pair $u, v$ is $r(u,v)$-connected if there are $r(u,v)$ edge-disjoint paths between $u$ and $v$. Similarly, in the vertex-connectivity version, a pair $u, v$ is $r(u,v)$-connected if there are $r(u,v)$ vertex-disjoint paths between $u$ and $v$. The edge-connectivity version of SNDP is known to have a factor 2 approximation. However, no non-trivial approximation algorithm has been known so far for the vertex version of SNDP, except for special cases of the problem.
We present an extremely simple randomized algorithm that achieves an $O(k^3 \log |T|)$-approximation for this problem, where $k$ denotes the maximum connectivity requirement, and $T$ is the set of vertices that participate in one or more pairs with non-zero connectivity requirements. We also give a simple proof of the recently discovered $O(k^2 \log |T|)$-approximation algorithm for the single-source version of vertex-connectivity SNDP. Our results establish a natural connection between vertex-connectivity and a well-understood generalization of edge-connectivity, namely, element-connectivity, in that an instance of vertex-connectivity SNDP can be reduced to a small number of instances of the element-connectivity SNDP.
A preliminary version of this paper appeared in the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2009.
Licensed under a Creative Commons Attribution License (CC-BY)