Approximating minimum size {1,2}-connected networks Original Research Article

The problem of finding the minimum size 2-connected subgraph is a classical problem in network design. It is known to be NP-hard even on cubic planar graphs and MAX SNP-hard. We study the generalization of this problem, 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 size subgraph satisfying these requirements. For both problems we give 32-approximation algorithms. This improves on the straightforward 2-approximation algorithms for these problems, and generalizes earlier results for 2-connectivity. We also give analyses of the classical local optimization heuristics for these two network design problems.