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 r ij = k for all i,j , we described a polynomial‐time algorithm that claimed to output a solution of cost no more than 2 H (k) times optimal, where H = 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+1) ‐vertex connected graph, gives solutions that are a factor Ω(k) away from the minimum.In the case r ij ∈ {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.
