Hardness of approximation for vertex-connectivity network design problems

摘要

In the survivable network design problem (SNDP), the goal is to find a minimum-cost spanning subgraph satisfying certain connectivity requirements. We study the vertex-connectivity variant of SNDP in which the input specifies, for each pair of vertices, a required number of vertex-disjoint paths connecting them.We give the first strong lower bound on the approximability of SNDP, showing that the problem admits no efficient 2log(1-epsilon) n ratio approximation for any fixed epsilon>0, unless NPsubset of or equal toDTIME(n(polylog)(n)). We show hardness of approximation results for some important special cases of SNDP, and we exhibit the first lower bound on the approximability of the related classical NP-hard problem of augmenting the connectivity of a graph using edges from a given set.