Two-Connected Spanning Subgraphs with at Most $\frac{10}{7}{OPT}$ Edges
Klaus Heeger, Jens Vygen · SIAM Journal on Discrete Mathematics · 2017
We present a $\frac{10}{7}$-approximation algorithm for the minimum 2-vertex-connected spanning subgraph problem. Similarly to the work of Cheriyan, Sebö, and Szigeti for 2-edge-connected spanning subgraphs, our algorithm is based on computing a carefully designed ear-decomposition.