ALCOMFT-TR-01-127

Piotr Krysta and Anil Kumar
Approximation Algorithms for Minimum Size 2-Connectivity Problems
MPI. Work packages 2 and 4. May 2001.

Abstract: We study some versions of the problem of finding the minimum size 2-connected subgraph. This problem is NP-hard (even on cubic planar graphs) and MAX SNP-hard. We show that the minimum 2-edge connected subgraph problem can be approximated to within (4)/(3)-epsilon for general graphs, improving upon the recent result of Vempala and Vetta. Better approximations are obtained for planar graphs and for cubic graphs. We also consider the generalization, where requirements of 1 or 2 edge or vertex disjoint paths are specified between every pair of vertices, and the aim is to find a minimum subgraph satisfying these requirements. We show that this problem can be approximated within (3)/(2), generalizing earlier results for 2-connectivity. We also analyse the classical local optimization heuristics. For cubic graphs, our results imply a new upper bound on the integrality gap of the linear programming formulation for the 2-edge connectivity problem.

Postscript file: ALCOMFT-TR-01-127.ps.gz (77 kb).