Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems

Abstract

The survivable network design problem (SNDP) is the following problem: given an undirected graph and values ri j for each pair of vertices i and j, find a minimum-cost subgraph such that there are at least ri j 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. The element connectivity problem (ELC-SNDP, or ELC) is a problem of intermediate difficulty. In this problem, the set of vertices is partitioned into terminals and nonterminals. The edges and nonterminals of the graph are called elements. The values ri j are only specified for pairs of terminals i, j, and the paths from i to j must be element disjoint. Thus if ri j - 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 and iteratively rounds solutions to a linear programming relaxation of the problem. ELC has a primal-dual O ( log k )-approximation algorithm, where k = maxi, j r i j. Since this work first appeared as an extended abstract, it has been shown that it is hard to approximate VC-SNDP to factor 2log1 - ε{lunate} n. In this paper we investigate applying iterative rounding to ELC and VC-SNDP. We show that iterative rounding will not yield a constant factor approximation algorithm for general VC-SNDP. On the other hand, we show how to extend the analysis of iterative rounding applied to EC-SNDP to yield 2-approximation algorithms for both general ELC, and for the case of VC-SNDP when ri j ∈ { 0, 1, 2 }. The latter result improves on an existing 3-approximation algorithm. The former is the first constant factor approximation algorithm for a general survivable network design problem that allows node failures. © 2006.