2026-08-12T05:29:48Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18081 2024-03-06T11:00:57Z ddc:004 open_access

A 4/3 Approximation for 2-Vertex-Connectivity Bosch-Calvo, Miguel Grandoni, Fabrizio Jabal Ameli, Afrouz Algorithm Network Design Vertex-Connectivity Approximation The 2-Vertex-Connected Spanning Subgraph problem (2VCSS) is among the most basic NP-hard (Survivable) Network Design problems: we are given an (unweighted) undirected graph G. Our goal is to find a subgraph S of G with the minimum number of edges which is 2-vertex-connected, namely S remains connected after the deletion of an arbitrary node. 2VCSS is well-studied in terms of approximation algorithms, and the current best (polynomial-time) approximation factor is 10/7 by Heeger and Vygen [SIDMA'17] (improving on earlier results by Khuller and Vishkin [STOC'92] and Garg, Vempala and Singla [SODA'93]). Here we present an improved 4/3 approximation. Our main technical ingredient is an approximation preserving reduction to a conveniently structured subset of instances which are "almost" 3-vertex-connected. The latter reduction might be helpful in future work. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Miguel Bosch-Calvo and Fabrizio Grandoni and Afrouz Jabal Ameli 2023 Is Part Of LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2023.29 urn:nbn:de:0030-drops-180813 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.29 eng https://creativecommons.org/licenses/by/4.0/legalcode