On directed Steiner trees

ABSTRACT

The directed Steiner tree problem is the following: given a directed graph G = (V, E) with weights on the edges, a set of terminals S ⊆ V, and a root vertex r, find a minimum weight out-branching T rooted at r, such that all vertices in S are included in T. This problem is known to be NP-hard. Recently, non-trivial polynomial time approximation algorithms have been developed for this problem with worst case approximation guarantees of O(k^ε) for any fixed ε > 0. We consider a natural LP relaxation of this problem. Using a dual formulation we construct a simple deterministic (D + 1)-approximation algorithm for a special case when the subgraph induced by V \ S is a tree with depth D (for example, this can be shown to include the group Steiner tree problem as a special case, by the loss of poly-log factors in the approximation guarantee). We also show that this LP has an integrality gap of Θ(√k) for the general problem.

REFERENCES

• 1: 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
• 2: Moses Charikar , Chandra Chekuri , To-yat Cheung , Zuo Dai , Ashish Goel , Sudipto Guha , Ming Li, Approximation algorithms for directed Steiner problems, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.192-200, January 25-27, 1998, San Francisco, California, United States
• 3: Moses Charikar , Chandra Chekuri , Ashish Goel , Sudipto Guha, Rounding via trees: deterministic approximation algorithms for group Steiner trees and k-median, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.114-123, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276719]
• 4: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 5: Naveen Garg , Goran Konjevod , R. Ravi, A polylogarithmic approximation algorithm for the Steiner group tree problem, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.253-259, January 25-27, 1998, San Francisco, California, United States
• 6: Robert Endre Tarjan, Data structures and network algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983
• 7: A. Zelikovsky, "A series of approximation algorithms for the acyclic directed Steiner tree problem", Algorithmica, 18(1):99-110, (1997).