Tech Report CS-92-21

Approximation Algorithms for Steiner Augmentations for Two-Connectivity

R. Ravi

April 1992

Abstract:

We consider the problem of increasing the connectivity of a given graph to two at optimal cost. Fredrickson and Ja'Ja' showed that that this problem is NP-hard and provide approximation algorithms. Recently, Khuller and Thirumella have extended these results and presented a more efficient version of the results of Fredrickson and Ja'Ja'. We consider an extension of this problem to a more general setting. In this setting, we are given an edge-weighted graph, a subset of the vertex set called the sites and an initial subgraph; the objective is to find a minimum weight augmentation of edges that makes the sites two edge-connected or vertex-connected. We provide approximation algorithms for the first time for these problems by extending those of Khuller and Thirumella with matching performance bounds. If the initial subgraph is pconnected, we find an augmentation of weight at most twice the optimal. Otherwise, the performance guarantee is three. The performance guarantee of three is obtained by an interesting application of an approximate min-max relation concerning Steiner trees and packing of cuts derived in a paper by Agrawal, Klein and Ravi.

(complete text in pdf or gzipped postscript)