A Better-Than-5/4-Approximation for Two-Edge Connectivity
Felix Hommelsheim, Alexander Lindermayr, Zhenwei Liu · Society for Industrial and Applied Mathematics eBooks · 2026
The 2-Edge-Connected Spanning Subgraph Problem (2ECSS) is a fundamental problem in survivable network design. Given an undirected 2-edge-connected graph, the goal is to find a 2-edge-connected spanning subgraph with the minimum number of edges; a graph is 2-edge-connected if it is connected after the removal of any single edge. 2ECSS is APX-hard and has been extensively studied in the context of approximation algorithms. Very recently, Bosch-Calvo, Garg, Grandoni, Hommelsheim, Jabal Ameli, and Lindermayr showed the currently best-known approximation ratio of \(^5\!/\!_4\) [STOC 2025]. This factor is tight for many of their techniques and arguments, and it was not clear whether \(^5\!/\!_4\) can be improved.