Network design for vertex connectivity

We study the survivable network design problem (SNDP) for vertex connectivity. Given a graph G(V,E) with costs on edges, the goal of SNDP is to find a minimum cost subset of edges that ensures a given set of pairwise vertex connectivity requirements. When all connectivity requirements are between a special vertex, called the source , and vertices in a subset T ⊆ V, called terminals , the problem is called the single-source SNDP. Our main result is a randomized k O(k 2 ) log 4 n-approximation algorithm for single-source SNDP where k denotes the largest connectivity requirement for any source-terminal pair. In particular, we get a poly-logarithmic approximation for any constant k. Prior to our work, no non-trivial approximation guarantees were known for this problem for any k ≥ 3. We also show that SNDP is k Ω(1) -hard to approximate and provide an elementary construction that shows that the well-studied set-pair linear programming relaxation for this problem has an Ω(k 1/3 ) integrality gap.

Authors

• Tanmoy Chakraborty 0001
• Julia Chuzhoy
• Sanjeev Khanna

Keywords

• network design
• hardness of approximation
• approximation algorithms
• vertex connectivity