Approximation Algorithms for Minimum Size 2-Connectivity Problems

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 $\frac{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 $\frac{3}{2}$, improving upon a straightforward
$2$-approximation and generalizing earlier results for 2-connectivity.
We also analyse the classical local optimization heuristics for these
network design problems. In fact all our algorithms use the local
optimization techniques. In the case of cubic graphs, our results
imply a new upper bound on the integrality gap of the natural linear
programming formulation for the 2-edge connectivity problem.
In this talk I will present an overview of the above results and will
talk in a more detail about some of them. Emphasis will be put on the
techniques used: lower bounding techniques, local search, DFS-based.

This is joint work with Anil Kumar.

Remark: As the duration time I have put 60 minutes (I guess it's better
to put an upper bound :-), but if fact I should be done earlier.