Key points are not available for this paper at this time.
We study the 2-edge-connected spanning subgraph (2-ECSS) problem: Given a graph G, compute a connected subgraph H of G with the minimum number of edges such that H is spanning, i. e. , V (H) = V (G), and H is 2-edge-connected, i. e. , H remains connected upon the deletion of any single edge, if such an H exists. The 2-ECSS problem is known to be NP-hard. In this work, we provide a polynomial-time (5 4 +) -approximation for the problem for an arbitrarily small >0, improving the previous best approximation ratio of 1310+. Our improvement is based on two main innovations: First, we reduce solving the problem on general graphs to solving it on structured graphs with high vertex connectivity. This high vertex connectivity ensures the existence of a 4-matching across any bipartition of the vertex set with at least 10 vertices in each part. Second, we exploit this property in a later gluing step, where isolated 2-edge-connected components need to be merged without adding too many edges. Using the 4-matching property, we can repeatedly glue a huge component (containing at least 10 vertices) to other components. This step is reminiscent of the Pac-Man game, where a Pac-Man (a huge component) consumes all the dots (other components) as it moves through a maze. These two innovations lead to a significantly simpler algorithm and analysis for the gluing step compared to the previous best approximation algorithm, which required a long and tedious case analysis.
Garg et al. (Fri,) studied this question.