2026-07-22T13:39:29Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19351 2024-03-06T11:03:50Z ddc:004 open_access

An Approximation Algorithm for Two-Edge-Connected Subgraph Problem via Triangle-Free Two-Edge-Cover Kobayashi, Yusuke Noguchi, Takashi approximation algorithm survivable network design minimum 2-edge-connected spanning subgraph triangle-free 2-matching 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. 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 a factor of 1.326, which is the best approximation ratio. In this paper, under the assumption that a maximum triangle-free 2-matching can be found in polynomial time in a graph, we give a (1.3+ε)-approximation algorithm for 2-ECSS, where ε is an arbitrarily small positive fixed constant. Note that a complicated polynomial-time algorithm for finding a maximum triangle-free 2-matching is announced by Hartvigsen in his PhD thesis, but it has not been peer-reviewed or checked in any other way. 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. Then, with the obtained triangle-free 2-edge-cover, we apply the arguments by Garg, Grandoni, and Ameli. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yusuke Kobayashi and Takashi Noguchi 2023 Is Part Of LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2023.49 urn:nbn:de:0030-drops-193514 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.49 eng https://creativecommons.org/licenses/by/4.0/legalcode