Network design for vertex connectivity

Abstract

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 kO(k2) log4n-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 Ω(k1/3) integrality gap.