Improved approximating algorithms for Directed Steiner Forest

ABSTRACT

We consider the k-Directed Steiner Forest (k-DSF) problem: given a directed graph G = (V, E) with edge costs, a collection D ∈ V x V of ordered node pairs, and an integer k ≤ |D|, find a min-cost subgraph H of G that contains an st-path for (at least) k pairs (s, t) ∈ D. When k = |D|, we get the Directed Steiner Forest (DSF) problem. The best known approximation ratios for these problems are: Õ(k^2/3) for k-DSF by Charikar et al. [2], and O(k^1/2+ε) for DSF by Chekuri et al. [3].

For DSF we give an O(n^ε·min {n^4/5,m^2/3})-approximation scheme using a novel LP-relaxation seeking to connect pairs via "cheap" paths. This is the first sublinear (in terms of n = |V|) approximation ratio for the problem. For k-DSF we give a simple greedy O(k^1/2+ε)-approximation scheme, improving the best known ratio Õ(k^2/3) by Charikar et al. [2], and (almost) matching, in terms of k, the best ratio known for the undirected variant [11]. Even when used for the particular case DSF, our algorithm favorably compares to the one of [3], which repeatedly solves linear programs, and uses complex time and space consuming transformations.

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: 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]
• 3: Chandra Chekuri , Guy Even , Anupam Gupta , Danny Segev, Set connectivity problems in undirected graphs and the directed Steiner network problem, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.532-541, January 20-22, 2008, San Francisco, California
• 4: Chandra Chekuri , Guy Even , Guy Kortsarz, A greedy approximation algorithm for the group Steiner problem, Discrete Applied Mathematics, v.154 n.1, p.15-34, 1 January 2006 [doi>10.1016/j.dam.2005.07.010]
• 5: 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]
• 6: 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]
• 7: G. Even. Recursive greedy methods, Ch. 5 in Approximation Algorithms and Metahueristics, T. F. Gonzales ed. Chapman and Hall/CRC, 2007.
• 8: U. Feige, G. Kortsarz, and D. Peleg. The dense k-Subgraph problem. Algorithmica, 29(3):410--421, 2001.
• 9: Naveen Garg, Saving an epsilon: a 2-approximation for the k-MST problem in graphs, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060650]
• 10: 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]
• 11: A. Gupta, M. T. Hajiaghayi, V. Nagarajan, and R. Ravi. Dial a Ride from k-Forest. In ESA, pages 241--252, 2007.
• 12: Mohammad Taghi Hajiaghayi , Kamal Jain, The prize-collecting generalized steiner tree problem via a new approach of primal-dual schema, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.631-640, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109626]
• 13: 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]
• 14: Refael Hassin, Approximation schemes for the restricted shortest path problem, Mathematics of Operations Research, v.17 n.1, p.36-42, Feb. 1992 [doi>10.1287/moor.17.1.36]
• 15: C. H. Helvig, G. Robins, and A. Zelikovsky. Improved approximation scheme for the group Steiner problem. Networks, 37(1):8--20, 2001.
• 16: K. Jain. Factor 2 approximation algorithm for the generalized Steiner network problem. Combinatorica, 21(1):39--60, 2001.
• 17: Subhash Khot, On the Unique Games Conjecture, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.3, October 23-25, 2005 [doi>10.1109/SFCS.2005.61]
• 18: Samir Khuller, Approximation algorithms for finding highly connected subgraphs, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
• 19: Philip Klein , R. Ravi, A nearly best-possible approximation algorithm for node-weighted Steiner trees, Journal of Algorithms, v.19 n.1, p.104-115, July 1995 [doi>10.1006/jagm.1995.1029]
• 20: G. Kortsarz and Z. Nutov. Approximating minimum cost connectivity problems, Ch. 58 in Approximation Algorithms and Metahueristics, T. F. Gonzales ed.,. Chapman & Hall/CRC, 2007.
• 21: Guy Kortsarz , Zeev Nutov, Tight approximation algorithm for connectivity augmentation problems, Journal of Computer and System Sciences, v.74 n.5, p.662-670, August, 2008 [doi>10.1016/j.jcss.2007.05.002]
• 22: Guy Kortsarz , David Peleg, Approximating the weight of shallow Steiner trees, Discrete Applied Mathematics, v.93 n.2-3, p.265-285, July 20, 1999 [doi>10.1016/S0166-218X(99)00111-0]
• 23: Z. Nutov. Approximating Steiner networks with node weights. In LATIN, pages 411--422, 2008.
• 24: David Peleg, Approximation algorithms for the Label-CoverMAX and Red-Blue Set Cover problems, Journal of Discrete Algorithms, v.5 n.1, p.55-64, March, 2007 [doi>10.1016/j.jda.2006.03.008]
• 25: Ran Raz, A Parallel Repetition Theorem, SIAM Journal on Computing, v.27 n.3, p.763-803, June 1998 [doi>10.1137/S0097539795280895]
• 26: Gabriel Robins , Alexander Zelikovsky, Tighter Bounds for Graph Steiner Tree Approximation, SIAM Journal on Discrete Mathematics, v.19 n.1, p.122-134, 2005 [doi>10.1137/S0895480101393155]
• 27: A. Zelikovsky. A series of approximation algorithms for the acyclic directed Steiner tree problem. Algorithmica, 18(1):99--110, 1997.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms