Augmenting the connectivity of a graph from 1 to 2

Trivially, this problem is equivalent to the Tree Augmentation Problem: Given a graph G(V,E) and a spanning tree T(V,E') of G, and a set F, F\cap E'=\emptyset, find a minimum size subset F'\subseteq F so that G'(V,E'\cup F') has no bridges (namely G' is 2 edge-connected). The problem is Max-Snp Hard.

Many well known 2 ratio approximation algorithms apply for this problem, including the iterative rounding method of Jain, and the Primal-Dual scheme of Goemans and
Williamson.

We give a 1.5 ratio approximation for the problem solving a central and one of the most basic problems in connectivity augmentation. The algorithm is purely combinatorial but highly complex. In this talk we will discuss * some * of the ingredients of a simpler 1.8 ratio approximation algorithm.

Joint Work with Even and Nutov