ICALP 2023

Best Paper Track A: A 4/3 Approximation for 2-Vertex-Connectivity

Jul 12, 2023, 3:40 PM

20m

Auditorium (HNF)

ICALP 2023 Award-Winning Papers

Speaker

Miguel Bosch Calvo

Description

Miguel Bosch Calvo, Fabrizio Grandoni and Afrouz Jabal Ameli

Best Paper Track A:

Abstract: 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.