Approximating Minimum-Size k -Connected Spanning Subgraphs via Matching
Joseph Cheriyan, Ramakrishna Thurimella · SIAM Journal on Computing · 2000
An efficient heuristic is presented for the problem of finding a minimum-size k-connected spanning subgraph of an (undirected or directed) simple graph G=(V,E). There are four versions of the problem, and the approximation 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)], minimum-size k-edge connected spanning subgraph of a directed graph 1 + [4/\sqrt{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: The number of edges required for augmenting a graph of minimum degree k to be 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 subgraph whose size is within a factor of ($1.5+\epsilon$) of minimum, where $\epsilon > 0$ is a constant.