Erratum: An approximation algorithm for minimum-cost vertex-connectivity problems

Abstract

There is an error in our paper "An Approximation Algorithm for Minimum-Cost Vertex-Connectivity Problems" (Algorithmica (1997), 18:21-43). In that paper we considered the following problem: given an undirected graph and values rij for each pair of vertices i and j, find a minimum-cost set of edges such that there are rij vertex-disjoint paths between vertices i and j. We gave approximation algorithms for two special cases of this problem. Our algorithms rely on a primal-dual approach which has led to approximation algorithms for many edge-connectivity problems. The algorithms work in a series of stages; in each stage an augmentation subroutine augments the connectivity of the current solution. The error is in a lemma for the proof of the performance guarantee of the augmentation subroutine. In the case rij = k for all i, j, we described a polynomial-time algorithm that claimed to output a solution of cost no more than 2H(k) times optimal, where H(n) = 1 + 1/2 + ... + 1/n. This result is erroneous. We describe an example where our primal-dual augmentation subroutine, when augmenting a k-vertex connected graph to a (k + l)-vertex connected graph, gives solutions that are a factor Ω(k) away from the minimum. In the case rij ∈ {0, 1,2} for all i, j, we gave a polynomial-time algorithm which outputs a solution of cost no more than three times the optimal. In this case we prove that the statement in the lemma that was erroneous for the k-vertex connected case does hold, and that the algorithm performs as claimed.