A 5/4-Approximation for Two-Edge Connectivity

2024/08/13 by Miguel Bosch-Calvo, Bosch-Calvo, Miguel, Fabrizio Grandoni +6 · 2 citations
Computer Science · Engineering · Materials Science · #05C40 #05C85 (Secondary) #68R10 #68W25 (Primary) 68W40 #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Energy Harvesting in Wireless Networks #F.2.2 #FOS: Computer and information sciences #FOS: Mathematics #Graphene research and applications #Interconnection Networks and Systems

paper · pdf · doi:10.48550/arxiv.2408.07019

openalex publication_date 2024/08/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The 2-Edge-Connected Spanning Subgraph problem (2ECSS) is among the most basic survivable network design problems: given an undirected and unweighted graph, the task is to find a spanning subgraph with the minimum number of edges that is 2-edge-connected (i.e., it remains connected after the removal of any single edge). 2ECSS is an NP-hard problem that has been extensively studied in the context of approximation algorithms. The best known approximation ratio for 2ECSS prior to this work was 1.3+ε, for any constant ε>0 [Garg, Grandoni, Jabal-Ameli'23; Kobayashi, Noguchi'23]. In this paper, we present a 5/4-approximation algorithm. Our algorithm is also faster for small values of ε: its running time is n^O(1) instead of n^O(1/ε).

Cited by

• Approximation Schemes for Planar Graph Connectivity Problems
• A Better-Than-2 Approximation for the Directed Tree Augmentation Problem

Related

• A Better-Than-5/4-Approximation for Two-Edge Connectivity
• Improved Approximation for Two-Edge-Connectivity
• A 4/3 Approximation for 2-Vertex-Connectivity
• A New Approximation Algorithm for the Minimum 2-Edge-Connected Spanning Subgraph Problem
• 9/7-Approximation for Two-Edge-Connectivity and Two-Vertex-Connectivity