A Better-Than-5/4-Approximation for Two-Edge Connectivity
Felix Hommelsheim, Alexander Lindermayr, Zhenwei Liu
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-edgeconnected 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.
We break this natural barrier and present a ( 5 /4 -η)-approximation algorithm, for some constant η ≥ 10 -6 . On a high level, we follow the approach of previous works: take a triangle-free 2-edge cover and transform it into a 2-edge-connected spanning subgraph by adding only a few additional edges. For ≥ 5 /4-approximations, one can heavily exploit that a 4-cycle in the 2-edge cover can "buy" one additional edge. This enables simple and nice techniques, but immediately fails for our improved approximation ratio. To overcome this, we design two complementary algorithms that perform well for different scenarios: one for few 4-cycles and one for many 4-cycles. Besides this, there appear more obstructions when breaching 5 /4, which we surpass via new techniques such as colorful bridge covering, rich vertices, and branching gluing paths.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
1 top-tier paper has cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
- A 5/4-Approximation for Two-Edge Connectivity cites A Better-Than-2 Approximation for Weighted Tree Augmentation
- A 5/4-Approximation for Two-Edge Connectivity cites Bridging the gap between tree and connectivity augmentation: unified and stronger approaches
- A 5/4-Approximation for Two-Edge Connectivity cites Local Search for Weighted Tree Augmentation and Steiner Tree
- A Better-Than-2 Approximation for the Directed Tree Augmentation Problem cites A 5/4-Approximation for Two-Edge Connectivity
- A Better-Than-2 Approximation for the Directed Tree Augmentation Problem cites A Better-Than-2 Approximation for Weighted Tree Augmentation
- A Better-Than-2 Approximation for the Directed Tree Augmentation Problem cites Bridging the gap between tree and connectivity augmentation: unified and stronger approaches
- A Better-Than-2 Approximation for the Directed Tree Augmentation Problem cites Local Search for Weighted Tree Augmentation and Steiner Tree
- A Better-Than-2 Approximation for Weighted Tree Augmentation cites Bridging the gap between tree and connectivity augmentation: unified and stronger approaches
- Local Search for Weighted Tree Augmentation and Steiner Tree cites Bridging the gap between tree and connectivity augmentation: unified and stronger approaches
Cited by top-tier papers1
Builds on9
- A (slightly) improved approximation algorithm for metric TSPAnna R. Karlin, Nathan Klein, Shayan Oveis GharanSTOC 2021 · 114 citations
- Local Search for Weighted Tree Augmentation and Steiner TreeVera Traub, Rico ZenklusenSODA 2022 · 27 citations
- Bridging the gap between tree and connectivity augmentation: unified and stronger approachesFederica Cecchetto, Vera Traub, Rico ZenklusenSTOC 2021 · 22 citations
- A Better-Than-2 Approximation for Weighted Tree AugmentationVera Traub, Rico ZenklusenFOCS 2021 · 20 citations
- A 5/4-Approximation for Two-Edge ConnectivityMiguel Bosch-Calvo, Mohit Garg, Fabrizio Grandoni, Felix Hommelsheim et al.STOC 2025 · 9 citations
Related papers
- Improved Approximation for Two-Edge-ConnectivityMohit Garg, Fabrizio Grandoni, Afrouz Jabal AmeliSODA 2023 · 5 citations
- Almost Tight Additive Guarantees for k-Edge-ConnectivityNikhil Kumar, Chaitanya SwamyFOCS 2025 · 4 citations
- Breaching the 2-approximation barrier for the forest augmentation problemFabrizio Grandoni, Afrouz Jabal Ameli, Vera TraubSTOC 2022 · 6 citations
- A Nearly Time-Optimal Distributed Approximation of Minimum Cost k-Edge-Connected Spanning SubgraphMichal Dory, Mohsen GhaffariSODA 2023 · 1 citation
- Survivable Network Design Revisited: Group-ConnectivityQingyun Chen, Bundit Laekhanukit, Chao Liao, Yuhao ZhangFOCS 2022 · 1 citation
