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 －ε for general graphs, improving upon the recent result of Vempala and Vetta [14]. 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.
展开▼
