Published: August 17, 2012

**Keywords:**approximation algorithms, survivable network design, vertex-connectivity

**Categories:**algorithms, approximation algorithms, networks, survivable networks, graphs, connectivity, vertex-connectivity, special issue, Motwani special issue

**ACM Classification:**F.2.2, G.1.6

**AMS Classification:**68Q25, 68W20, 68W25

**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.