On approximability of the minimum-cost k-connected spanning subgraph problem
Artur Czumaj, Andrzej Lingas · 1999
We present the first truly polynomial-time approximation scheme (PTAS) for the minimum-cost k-vertex- (or, k- edge-) connected spanning subgraph problem for complete Euclidean graphs in R d : Previously it was known for every positive constant " how to construct in a polynomial time a graph on a superset of the input points which is k-vertex connected with respect to the input points, and whose cost is within (1+ ") of the minimum-cost of a k-vertex connected graph spanning the input points. We subsume that result by showing for every positive constant " how to construct in a polynomial-time a k-connected subgraph spanning the input points without any Steiner points and having the cost within (1 + ") of the minimum. We also study hardness of approximations for the minimum-cost k-vertex- and k-edge-connected spanning subgraph problems. The only inapproximability result known so far for the minimum-cost k-vertex- and k-edge- connected spanning subgraph problems states that the k- e...