A $4/3$ Approximation for $2$-Vertex-Connectivity
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911030581395456 |
|---|---|
| author | Bosch-Calvo, Miguel Grandoni, Fabrizio Ameli, Afrouz Jabal |
| author_facet | Bosch-Calvo, Miguel Grandoni, Fabrizio Ameli, Afrouz Jabal |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2305_02240 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | A $4/3$ Approximation for $2$-Vertex-Connectivity Bosch-Calvo, Miguel Grandoni, Fabrizio Ameli, Afrouz Jabal Data Structures and Algorithms 68W25 (Primary) 68W40, 68R10, 05C40, 05C85 (Secondary) F.2.2 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. |
| title | A $4/3$ Approximation for $2$-Vertex-Connectivity |
| topic | Data Structures and Algorithms 68W25 (Primary) 68W40, 68R10, 05C40, 05C85 (Secondary) F.2.2 |
| url | https://arxiv.org/abs/2305.02240 |