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.

Published in:
Proceedings of the 8th Workshop on Approximation and Online Algorithms (WAOA), to appear
Presented at:
ALGO 2010: 8th Workshop on Approximation and Online Algorithms (WAOA), University of Liverpool, UK, September 9-10, 2010
Springer-Verlag New York, Ms Ingrid Cunningham, 175 Fifth Ave, New York, Ny 10010 Usa

 Record created 2010-08-24, last modified 2019-03-16

Download fulltext

Rate this document:

Rate this document:
(Not yet reviewed)