Improved Approximation for Two-Edge-Connectivity

Download PDF

The basic goal of survivable network design is to construct low-cost networks which preserve a sufficient level of connectivity despite the failure or removal of a few nodes or edges. One of the most basic problems in this area is the 2-Edge-Connected Spanning Subgraph problem (2-ECSS): given an undirected graph G, find a 2-edge-connected spanning subgraph H of G with the minimum number of edges (in particular, H remains connected after the removal of one arbitrary edge).
2-ECSS is NP-hard and the best-known (polynomial-time) approximation factor for this problem is 4/3. Interestingly, this factor was achieved with drastically different techniques by [Hunkenschr{ö}der, Vempala and Vetta '00,'19] and [Seb{ö} and Vygen, '14]. In this paper we present an improved \frac{118}{89}+\epsilon<1.326 approximation for 2-ECSS.
The key ingredient in our approach (which might also be helpful in future work) is a reduction to a special type of structured graphs: our reduction preserves approximation factors up to 6/5. While reducing to 2-vertex-connected graphs is trivial (and heavily used in prior work), our structured graphs are "almost" 3-vertex-connected: more precisely, given any 2-vertex-cut \{u,v\} of a structured graph G=(V,E), G[V\setminus \{u,v\}] has exactly 2 connected components, one of which contains exactly one node of degree 2 in G.