Approximation schemes for minimum 2-edge-connected and biconnected subgraphs in planar graphs
Artur Czumaj, Michelangelo Grigni, Papa A. Sissokho, Hairong Zhao · 2004
Given an undirected graph, finding either a minimum 2-edge-connected spanning subgraph or a minimum 2-vertex-connected (biconnected) spanning subgraph is MaxSNP-hard. We show that for planar graphs, both problems have a polynomial time approximation scheme (PTAS) with running time n O(1/ε),wherenis the graph size and ε is the relative error allowed. When the planar graph has edge costs, we approximately solve the analogous min-cost subgraph problems in time n O(γ/ε),whereγis the ratio of the total edge cost to the optimum solution cost. 1