A Unified Approach for Approximating 2-Edge-Connected Spanning Subgraph and 2-Vertex-Connected Spanning Subgraph

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 both $\frac{4}{3}$. Using a common theme, the algorithms and their analyses are very similar.

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