9/7-Approximation for Two-Edge-Connectivity and Two-Vertex-Connectivity

Abstract

We provide algorithms for the minimum 2-edge-connected spanning subgraph problem and the minimum 2-vertex-connected spanning subgraph problem with approximation ratio $\frac{9}{7}$. This improves upon a recent algorithm with ratio slightly smaller than $\frac{4}{3}$ for 2-edge-connectivity, and another one with ratio $\frac{4}{3}$ for 2-vertex-connectivity.

This was an early and insufficiently verified attempt. Errors affecting the main results were later identified, and the manuscript has been withdrawn