An Improved Approximation Algorithm for Minimum Size 2-Edge Connected Spanning Subgraphs

We give a 17 12 -approximation algorithm for the following NP-hard problem: Given an undirected graph, find a 2-edge connected spanning subgraph that has the minimum number of edges. The best previous approximationguarantee was 3 2 . We conjecture that there is a 4 3 -approximation algorithm. Thus our main result gets half-way to this target. 1 Introduction Given an undirected graph, consider the problem of finding a 2-edge connected spanning subgraph that has the minimum number of edges. The problem is NP-hard, since the Hamiltonian cycle problem reduces to it. A number of recent papers have focused on approximation algorithms 1 for this and other related problems. We use the abbreviation 2-ECSS for 2-edge connected spanning subgraph. Here is an easy 2-approximation algorithm for the problem: Take an ear decomposition of the given graph (see Section 2 for definitions), and discard all 1-ears (ears that consist of one edge). Then the resulting graph is 2-edge connected and has at..