Miguel Bosch-Calvo ; Fabrizio Grandoni ; Afrouz Jabal Ameli - A $4/3$ Approximation for $2$-Vertex-Connectivity

theoretics:12721 - TheoretiCS, June 16, 2025, Volume 4 - https://doi.org/10.46298/theoretics.25.13
A $4/3$ Approximation for $2$-Vertex-ConnectivityArticle

Authors: Miguel Bosch-Calvo ORCID; Fabrizio Grandoni ORCID; Afrouz Jabal Ameli ORCID

    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 spanning 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.


    Volume: Volume 4
    Published on: June 16, 2025
    Accepted on: March 30, 2025
    Submitted on: December 20, 2023
    Keywords: Data Structures and Algorithms,68W25 (Primary) 68W40, 68R10, 05C40, 05C85 (Secondary),F.2.2

    Consultation statistics

    This page has been seen 82 times.
    This article's PDF has been downloaded 50 times.