An Approximation Algorithm for Minimum-Cost Vertex-Connectivity Problems

Abstract

We present an approximation algorithm for solving graph problems in which a low-cost set of edges must be selected that has certain vertex-connectivity properties. In the survivable network design problem, a value rij for each pair of vertices i and j is given, and a minimum-cost set of edges such that there are rij vertex-disjoint paths between vertices i and j must be found. In the case for which rij ∈ {0, 1, 2} for all i, j, we can find a solution of cost no more than three times the optimal cost in polynomial time. In the case in which rij = k for all i, j, we can find a solution of cost no more than 2H(k) times optimal, where H(n) = 1 + 1/2 + ⋯ + 1/2. No approximation algorithms were previously known for these problems. Our algorithms rely on a primal-dual approach which has recently led to approximation algorithms for many edge-connectivity problems.