An iterative rounding 2-approximation algorithm for the element connectivity problem

In the survivable network design problem (SNDP), given an undirected graph and values r(ij) for each pair of vertices i and j, we attempt to find a minimum-cost subgraph such that there are r(ij) disjoint paths between vertices i and j. In the edge connected version of this problem (EC-SNDP), these paths must be edge-disjoint. In the vertex connected version of the problem (VC-SNDP), the paths must be vertex disjoint. Jain et al. [12] propose a version of the problem intermediate in difficulty to these two, called the element connectivity problem (ELC-SNDP, or ELC). In this problem, the set of vertices is partitioned into terminals and nonterminals. Phe edges and nonterminals of the graph are called elements. The values r(ij) are only specified for pairs of terminals i, j, and the paths from i to j must be element disjoint. Thus if r(ij)-1 elements fail, terminals i and j are still connected by a path in the network. These variants of SNDP are all known to be NP-hard. The best known approximation algorithm for the EC-SNDP has performance guarantee of 2 (due to Jain [11]), and iteratively rounds solutions to a linear programming relaxation of i the problem. ELC has a primal-dual O(log k)-approximation algorithm, where k = max(i,j) r(ij) (Jain et al. [12]). VC-SNDP is not known to have a non-trivial approximation algorithm; however, recently Fleischer [7] has shown how to extend the technique of Jain [11] to give a 2-approximation algorithm in the case that r(ij) is an element of {0, 1, 2}. She also, shows that the same techniques will not work for VC-SNDP for more general values of r(ij). In this paper we show that these techniques can be extended to a 2-approximation algorithm for ELC. This gives the first constant approximation algorithm for a general survivable network design problem which allows node failures.