Approximating minimum-size k-connected spanning subgraphs via matching

An efficient heuristic is presented for the problem of finding a minimum-si ze k-connected spanning subgraph of an (undirected or directed) simple grap h G = ( V, E). There are four versions of the problem, and the approximatio n guarantees are as follows: minimum-size k-node connected spanning subgraph of an undirected graph 1 [1/k], minimum-size k-node connected spanning subgraph of a directed graph 1 + [1/ k], minimum-size k-edge connected spanning subgraph of an undirected graph 1 [2/(k + 1)], and minimum-size k-edge connected spanning subgraph of a directed graph 1 + [4/ root k]. The heuristic is based on a subroutine for the degree-constrained subgraph (b-matching) problem. It is simple and deterministic and runs in time O (k\ E\(2)). The following result on simple undirected graphs is used in the analysis: T he number of edges required for augmenting a graph of minimum degree k to b e k-edge connected is at most k\V\/(k+1). For undirected graphs and k = 2, a ( deterministic) parallel NC version of the heuristic finds a 2-node connected (or 2-edge connected) spanning subgr aph whose size is within a factor of (1.5 + epsilon) of minimum, where epsi lon > 0 is a constant.