Hardness of Approximation for Vertex-Connectivity Network Design Problems

2004/01/01 by Guy Kortsarz, Robert Krauthgamer, James R. Lee · 8 citations
Computer Science · #Complexity and Algorithms in Graphs #Advanced Graph Theory Research #Optimization and Search Problems

paper · doi:10.1137/s0097539702416736

Abstract

In the survivable networkdesign 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-ε n ratio approximation for any fixed ε > 0, unless \NP⊆ \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.

Citations

• Approximation Algorithms for Several Graph Augmentation Problems
• A threshold of ln <i>n</i> for approximating set cover
• Augmentation Problems

Cited by

• Approximation Schemes for Planar Graph Connectivity Problems
• Approximating minimum-cost edge-covers of crossing biset-families
• A Deterministic Algorithm for the Vertex Connectivity Survivable Network\n Design Problem
• Approximating (Unweighted) Tree Augmentation via Lift-and-Project, Part II
• Approximating (Unweighted) Tree Augmentation via Lift-and-Project, Part I: Stemless TAP
• A Better-Than-2 Approximation for the Directed Tree Augmentation Problem
• Approximating subset k-connectivity problems
• Domination in graphs with bounded propagation: algorithms, formulations and hardness results

Related

• An O(k³ log n)-Approximation Algorithm for Vertex-Connectivity Survivable Network Design
• A Deterministic Algorithm for the Vertex Connectivity Survivable Network\n Design Problem
• The Parameterized Complexity of the Survivable Network Design Problem
• Survivable Network Design Revisited: Group-Connectivity
• A note on the Survivable Network Design Problem