Theory of Computing
-------------------
Title : An $O(k^3\log n)$-Approximation Algorithm for Vertex-Connectivity Survivable Network Design
Authors : Julia Chuzhoy and Sanjeev Khanna
Volume : 8
Number : 18
Pages : 401-413
URL : http://www.theoryofcomputing.org/articles/v008a018
Abstract
--------
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.