An Approximation Algorithm for Two-Edge-Connected Subgraph Problem via Triangle-free Two-Edge-Cover

04/26/2023

∙

by   Yusuke Kobayashi, et al.

∙

0

∙

share

The 2-Edge-Connected Spanning Subgraph problem (2-ECSS) is one of the most fundamental and well-studied problems in the context of network design. In the problem, we are given an undirected graph G, and the objective is to find a 2-edge-connected spanning subgraph H of G with the minimum number of edges. For this problem, a lot of approximation algorithms have been proposed in the literature. In particular, very recently, Garg, Grandoni, and Ameli gave an approximation algorithm for 2-ECSS with factor 1.326, which was the best approximation ratio. In this paper, we give a (1.3+ε)-approximation algorithm for 2-ECSS, where ε is an arbitrary positive fixed constant, which improves the previously known best approximation ratio. In our algorithm, we compute a minimum triangle-free 2-edge-cover in G with the aid of the algorithm for finding a maximum triangle-free 2-matching given by Hartvigsen. Then, with the obtained triangle-free 2-edge-cover, we apply the arguments by Garg, Grandoni, and Ameli.