Set connectivity problems in undirected graphs and the directed Steiner network problem

ABSTRACT

In the generalized connectivity problem, we are given an edge-weighted graph G = (V, E) and a collection D = {(S₁,T₁),…, (S_k,T_k)} of distinct demands; each demand (S_i, T_i) is a pair of disjoint vertex subsets. We say that a subgraph F ⊆ G connects a demand (S_i, T_i) when it contains a path with one endpoint in S_i and the other in T_i. The goal is to identify a minimum weight subgraph that connects all demands in D. Alon et al. (SODA '04) introduced this problem to study online network formation settings and showed that it captures some well-studied problems such as Steiner forest, non-metric facility location, tree multicast, and group Steiner tree. Finding a non-trivial approximation ratio for generalized connectivity was left as an open problem. Our starting point is the first polylogarithmic approximation for generalized connectivity attaining a performance guarantee of O(log² n log² k). Here n is the number of vertices in G and k is the number of demands. We also prove that the cut-covering relaxation of this problem has an O(log³ n log² k) integrality gap.

Building upon the results for generalized connectivity we obtain improved approximation algorithms for two problems that contain generalized connectivity as a special case. For the directed Steiner network problem, we obtain an O(k^1/2+ε) approximation, which improves on the currently best performance guarantee of O(k^2/3) due to Charikar et al. (SODA '98). For the set connector problem, recently introduced by Fukunaga and Nagamochi (IPCO '07), we present a polylogarithmic approximation; this result improves on the previously known ratio which can be Ω(n) in the worst case.

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: Noga Alon , Baruch Awerbuch , Yossi Azar , Niv Buchbinder , Joseph (Seffi) Naor, A general approach to online network optimization problems, ACM Transactions on Algorithms (TALG), v.2 n.4, p.640-660, October 2006 [doi>10.1145/1198513.1198522]
• 3: Y. Bartal, Probabilistic approximation of metric spaces and its algorithmic applications, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.184, October 14-16, 1996
• 4: Yair Bartal, On approximating arbitrary metrices by tree metrics, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.161-168, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276725]
• 5: Moses Charikar , Chandra Chekuri, Approximation algorithms for directed Steiner problems, Journal of Algorithms, v.33 n.1, p.73-91, Oct. 1999 [doi>10.1006/jagm.1999.1042 ]
• 6: C. Chekuri , M. T. Hajiaghayi , G. Kortsarz , M. R. Salavatipour, Approximation Algorithms for Non-Uniform Buy-at-Bulk Network Design, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.677-686, October 21-24, 2006 [doi>10.1109/FOCS.2006.15]
• 7: C. Chekuri , M. T. Hajiaghayi , G. Kortsarz , M. R. Salavatipour, Approximation algorithms for node-weighted buy-at-bulk network design, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.1265-1274, January 07-09, 2007, New Orleans, Louisiana
• 8: Yevgeniy Dodis , Sanjeev Khanna, Design networks with bounded pairwise distance, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.750-759, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301447]
• 9: Jittat Fakcharoenphol , Satish Rao , Kunal Talwar, A tight bound on approximating arbitrary metrics by tree metrics, Journal of Computer and System Sciences, v.69 n.3, p.485-497, November 2004 [doi>10.1016/j.jcss.2004.04.011]
• 10: T. Fukunaga and H. Nagamochi. The set connector problem in graphs. In Proceedings of the 12th International Conference on Integer Programming and Combinatorial Optimization, pages 484--498. 2007.
• 11: Naveen Garg , Goran Konjevod , R. Ravi, A polylogarithmic approximation algorithm for the group Steiner tree problem, Journal of Algorithms, v.37 n.1, p.66-84, Oct. 2000 [doi>10.1006/jagm.2000.1096 ]
• 12: Michel X. Goemans , David P. Williamson, A General Approximation Technique for Constrained Forest Problems, SIAM Journal on Computing, v.24 n.2, p.296-317, April 1995 [doi>10.1137/S0097539793242618]
• 13: 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
• 14: M. T. Hajiaghayi, G. Kortsarz, and M. R. Salavatipour. Approximating buy-at-bulk and shallow-light k-Steiner trees. In Proceedings of the 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, pages 152--163, 2006
• 15: Eran Halperin , Guy Kortsarz , Robert Krauthgamer , Aravind Srinivasan , Nan Wang, Integrality Ratio for Group Steiner Trees and Directed Steiner Trees, SIAM Journal on Computing, v.36 n.5, p.1494-1511, December 2006 [doi>10.1137/S0097539704445718]
• 16: Eran Halperin , Robert Krauthgamer, Polylogarithmic inapproximability, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780628]
• 17: Dorit S. Hochbaum, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
• 18: D. S. Johnson. Approximation algorithms for combinatorial problems. Journal of Computer and System Sciences, 9(3):256--278, 1974.
• 19: Vijay V. Vazirani, Approximation algorithms, Springer-Verlag New York, Inc., New York, NY, 2001
• 20: A. Zelikovsky. A series of approximation algorithms for the acyclic directed Steiner tree problem. Algorithmica, 18(1):99--110, 1997.
• 21: Leonid Zosin , Samir Khuller, On directed Steiner trees, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.59-63, January 06-08, 2002, San Francisco, California