Improving on the 1. 5-approximation of a smallest 2-edge connected spanning subgraph (Q2706198)

Finding a minimum size spanning 2-edge-connected subgraph in a 2-edge-connected graph is NP-hard as the Hamiltonian cycle problem is a special case of this problem. It is easy to find a spanning 2-edge-connected subgraph with no more than twice the optimum number of edges: simply find an ear-decomposition of \(G\) and leave out all the trivial ears (those that are just an edge). Khuller and Vishkin gave a 1.5-approximation algorithm for the problem based on depth-first search. In the current paper the authors give a \({17\over 12}\)-approximation algorithm for the problem based on a result of A. Frank on the minimum number of even ears in an ear-decomposition of a 2-edge-connected graph. Recently Vempala and Vetta have improved the best approximation guarantee to \({4\over 3}\) [\textit{S. Vempala} and \textit{A. Vetta}, Factor \({4\over 3}\) approximations for minimum 2-connected subgraphs, in Proceedings of the Third International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, Max-Plank-Institut für Informatik, Saarbrücken, Germany; Springer, Berlin, 262-273 (2000)].