Approximating the Smallest k-Edge Connected Spanning Subgraph by LP-Rounding

摘要

The smallest k-ECSS problem is, given a graph along with an integer k, find a spanning subgraph that is Ac-edge connected and contains the fewest possible number of edges. We examine a natural approximation algorithm based on rounding an LP solution. A tight bound on the approximation ratio is 1 + 3/k for undirected graphs with k > 1 odd, 1 +2/k for undirected graphs with k even, and 1 +2/k for directed graphs with k arbitrary. Using iterated rounding improves the first upper bound to 1 +2/k. On the hardness side we show that for some absolute constant c > 0, for any integer k ≥ 2 (k ≥ 1), a polynomial-time algorithm approximating the smallest k-ECSS on undirected (directed) multigraphs to within ratio 1+c/k would imply P = NP.