A Better-Than-5/4-Approximation for Two-Edge Connectivity
Abstract
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.
Fields of Study & Subjects
Complexity and Algorithms in Graphs
Advanced Optical Network Technologies
Vehicle Routing Optimization Methods
Publication details
- Journal / source
- Society for Industrial and Applied Mathematics eBooks
- Publisher
- Society for Industrial and Applied Mathematics
- Pages
- 1468–1520
- Publication date
- 1 January 2026
- Language
- EN