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 k^O(k2) log⁴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.

REFERENCES

• 1: Ajit Agrawal , Philip Klein , R. Ravi, When Trees Collide: An Approximation Algorithm for theGeneralized Steiner Problem on Networks, SIAM Journal on Computing, v.24 n.3, p.440-456, June 1995 [doi>10.1137/S0097539792236237]
• 2: Sanjeev Arora , Carsten Lund , Rajeev Motwani , Madhu Sudan , Mario Szegedy, Proof verification and the hardness of approximation problems, Journal of the ACM (JACM), v.45 n.3, p.501-555, May 1998 [doi>10.1145/278298.278306]
• 3: Sanjeev Arora , Shmuel Safra, Probabilistic checking of proofs: a new characterization of NP, Journal of the ACM (JACM), v.45 n.1, p.70-122, Jan. 1998 [doi>10.1145/273865.273901]
• 4: V. Auletta, Y. Dinitz, Z. Nutov, and D. Parente. A 2-approximation algorithm for finding an optimum 3-vertex-connected spanning subgraph. Journal of Algorithms, 32(1):21--30, 1999.
• 5: Marshall Bern , Paul Plassmann, The steiner problem with edge lengths 1 and 2,, Information Processing Letters, v.32 n.4, p.171-176, Sept 1, 1989 [doi>10.1016/0020-0190(89)90039-2]
• 6: J. Cheriyan, T. Jordan, and Z. Nutov. On rooted node-connectivity problems. Algorithmica, 30(3):353--375, 2001.
• 7: J. Cheriyan, S. Vempala, and A. Vetta. An approximation algorithm for the minimum-cost k-vertex connected subgraph. SIAM Journal of Computing, 32(4):1050--1055, 2003.
• 8: Joseph Cheriyan , Santosh Vempala† , Adrian Vetta, Network Design Via Iterative Rounding Of Setpair Relaxations, Combinatorica, v.26 n.3, p.255-275, June 2006 [doi>10.1007/s00493-006-0016-z]
• 9: Y. Dinitz and Z. Nutov. A 3-approximation algorithm for finding optimum 4, 5-vertex-connected spanning subgraphs. Journal of Algorithms, 32(1):31--40, 1999.
• 10: Jittat Fakcharoenphol , Bundit Laekhanukit, An o(log² k)-approximation algorithm for the k-vertex connected spanning subgraph problem, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada [doi>10.1145/1374376.1374401]
• 11: Lisa Fleischer , Kamal Jain , David P. Williamson, Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems, Journal of Computer and System Sciences, v.72 n.5, p.838-867, August 2006 [doi>10.1016/j.jcss.2005.05.006]
• 12: András Frank , Tibor Jordán, Minimal edge-coverings of pairs of sets, Journal of Combinatorial Theory Series B, v.65 n.1, p.73-110, Sept. 1995 [doi>10.1006/jctb.1995.1044]
• 13: A. Frank and E. Tardos. An application of submodular flows. Linear Algebra and its Applications, 114-115:329--348, 1989.
• 14: Michel X. Goemans , David P. Williamson, The primal-dual method for approximation algorithms and its application to network design problems, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
• 15: M. X. Goemans , A. V. Goldberg , S. Plotkin , D. B. Shmoys , É. Tardos , D. P. Williamson, Improved approximation algorithms for network design problems, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.223-232, January 23-25, 1994, Arlington, Virginia, United States
• 16: M. X. Goemans, M. Mihail, V. Vazirani, and D. P. Williamson. A primal-dual approximation algorithm for generalized steiner network problems. Combinatorica, 15(3):435--454, 1995.
• 17: Kamal Jain, A Factor 2 Approximation Algorithm for the Generalized Steiner Network Problem, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.448, November 08-11, 1998
• 18: Samir Khuller , Balaji Raghavachari, Improved approximation algorithms for uniform connectivity problems, Journal of Algorithms, v.21 n.2, p.434-450, Sept. 1996 [doi>10.1006/jagm.1996.0052]
• 19: Guy Kortsarz , Robert Krauthgamer , James R. Lee, Hardness of Approximation for Vertex-Connectivity Network Design Problems, SIAM Journal on Computing, v.33 n.3, p.704-720, 2004 [doi>10.1137/S0097539702416736]
• 20: G. Kortsarz and Z. Nutov. Approximating node connectivity problems via set covers. Algorithmica, 37(2):75--92, 2003.
• 21: Guy Kortsarz , Zeev Nutov, Approximating k-node Connected Subgraphs via Critical Graphs, SIAM Journal on Computing, v.35 n.1, p.247-257, 2005 [doi>10.1137/S0097539703435753]
• 22: W. Mader. Endlichkeitsätze für k-kritische graphen (german). Mathematische Annalen, 229:143--153, 1977.
• 23: R. Ravi and D. P. Williamson. An approximation algorithm for minimum-cost vertex-connectivity problems. Algorithmica, 18(1):21--43, 1997.
• 24: Ran Raz, A Parallel Repetition Theorem, SIAM Journal on Computing, v.27 n.3, p.763-803, June 1998 [doi>10.1137/S0097539795280895]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

General Terms:
Algorithms, Theory

Keywords:
approximation algorithms, hardness of approximation, network design, vertex connectivity