k-Edge-Connectivity: Approximation and LP Relaxation

This paper's focus is the following family of problems, denoted k-ECSS, where k denotes a positive integer: given a graph (V, E) and costs for each edge, find a minimum-cost subset F of E such that (V, F) is k-edge-connected. For k=1 it is the spanning tree problem which is in P; for every other k it is APX-hard and has a 2-approximation. Moreover, assuming P != NP, it is known that for unit costs, the best possible approximation ratio is 1 + Theta(1/k) for k>1. Our first main result is to determine the analogous asymptotic ratio for general costs: we show there is a constant eps>0 so that for all k>1, finding a (1+eps)-approximation for k-ECSS is NP-hard. Thus we establish a gap between the unit-cost and general-cost versions, for large enough k. Next, we consider the multi-subgraph cousin of k-ECSS, in which we are allowed to buy arbitrarily many copies of any edges (i.e., F is now a multi-subset of E, with parallel copies having the same cost as the original edge). Not so much is known about this natural variant, but we conjecture that a (1 + Theta(1/k))-approximation algorithm exists, and we describe an approach based on its naive linear programming relaxation (LP) and graph decompositions. The LP is well-known --- it is essentially the same as the Held-Karp TSP and the undirected LP for Steiner tree --- and in order to further our understanding, we give a family of extreme points for this LP with exponentially bad fractionality.