Hardness of approximation for vertex-connectivity network design problems. (English) Zbl 1101.68985
Summary: 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 \(2^{\log^{1-\epsilon} n}\) ratio approximation for any fixed \(\epsilon > 0\), unless \(\text{NP}\subseteq \text{DTIME}(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.
We give the first strong lower bound on the approximability of SNDP, showing that the problem admits no efficient \(2^{\log^{1-\epsilon} n}\) ratio approximation for any fixed \(\epsilon > 0\), unless \(\text{NP}\subseteq \text{DTIME}(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.
MSC:
68W25 | Approximation algorithms |
05C85 | Graph algorithms (graph-theoretic aspects) |
05C40 | Connectivity |