Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2605.10058 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910207760662528 |
|---|---|
| author | Kobayashi, Yusuke Noguchi, Takashi |
| author_facet | Kobayashi, Yusuke Noguchi, Takashi |
| contents | In the 2-Vertex-Connected Spanning Subgraph problem (2-VCSS), we are given an undirected graph $G$, and the objective is to find a 2-vertex-connected spanning subgraph $S$ of $G$ with the minimum number of edges. In the context of survivable network design, 2-VCSS is one of the most fundamental and well-studied problems. There has been active research on improving the approximation ratio of algorithms, and the current best ratio is $\frac{4}{3}$, achieved by Bosch-Calvo, Grandoni, and Jabal Ameli. In this paper, we improve the approximation ratio to $\frac{95}{72}+\varepsilon$ ($<1.32$). The key idea in our algorithm is to introduce a 2-edge-cover without certain cycle components, and use it as an initial solution. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_10058 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | An Approximation Algorithm for 2-Vertex-Connectivity via Cycle-Restricted 2-Edge-Covers Kobayashi, Yusuke Noguchi, Takashi Data Structures and Algorithms In the 2-Vertex-Connected Spanning Subgraph problem (2-VCSS), we are given an undirected graph $G$, and the objective is to find a 2-vertex-connected spanning subgraph $S$ of $G$ with the minimum number of edges. In the context of survivable network design, 2-VCSS is one of the most fundamental and well-studied problems. There has been active research on improving the approximation ratio of algorithms, and the current best ratio is $\frac{4}{3}$, achieved by Bosch-Calvo, Grandoni, and Jabal Ameli. In this paper, we improve the approximation ratio to $\frac{95}{72}+\varepsilon$ ($<1.32$). The key idea in our algorithm is to introduce a 2-edge-cover without certain cycle components, and use it as an initial solution. |
| title | An Approximation Algorithm for 2-Vertex-Connectivity via Cycle-Restricted 2-Edge-Covers |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2605.10058 |