A 17/12-Approximation Algorithm for 2-Vertex-Connected Spanning Subgraphs on Graphs with Minimum Degree At Least 3
arXiv:1612.04790
Abstract
We obtain a polynomial-time 17/12-approximation algorithm for the minimum-cost 2-vertex-connected spanning subgraph problem, restricted to graphs of minimum degree at least 3. Our algorithm uses the framework of ear-decompositions for approximating connectivity problems, which was previously used in algorithms for finding the smallest 2-edge-connected spanning subgraph by Cheriyan, Sebő and Szigeti (SIAM J.Discrete Math. 2001) who gave a 17/12-approximation algorithm for this problem, and by Sebő and Vygen (Combinatorica 2014), who improved the approximation ratio to 4/3.
Revised Lemma 1 and Theorem 2, results unchanged