Approximation Algorithms for Directed Steiner Problems

TLDR

Directed Steiner tree and generalized Steiner network problems are key network design challenges, previously limited to trivial O(k) approximations, with related problems reducible to them and known to be as hard as set cover. The authors present the first nontrivial approximation algorithms for the directed Steiner tree and generalized Steiner network problems on general directed graphs. They develop a family of algorithms achieving an i(i−1)k^{1/i} approximation in O(n i k^{2i}) time for the Steiner tree, and an O(k^{2/3} log^{1/3} k) approximation for the generalized Steiner network. These algorithms yield polynomial‑time O(k^ε) approximations for any ε>0, quasi‑polynomial O(log^2 k) approximations, and extend nontrivial approximations to related problems.

Abstract

We give the first nontrivial approximation algorithms for the Steiner tree problem and the generalized Steiner network problem on general directed graphs. These problems have several applications in network design and multicast routing. For both problems, the best ratios known before our work were the trivial O(k)-approximations. For the directed Steiner tree problem, we design a family of algorithms that achieves an approximation ratio of i(i − 1)k1/i in time O(nik2i) for any fixed i > 1, where k is the number of terminals. Thus, an O(kϵ) approximation ratio can be achieved in polynomial time for any fixed ϵ > 0. Setting i = log k, we obtain an O(log2 k) approximation ratio in quasi-polynomial time. For the directed generalized Steiner network problem we give an algorithm that achieves an approximation ratio of O(k2/3log1/3k), where k is the number of pairs of vertices that are to be connected. Related problems including the group Steiner tree problem, the set TSP problem, and several others in both directed and undirected graphs can be reduced in an approximation preserving fashion to the directed Steiner tree problem. Thus, we obtain the first nontrivial approximations to those as well. All these problems are known to be as hard as the Set cover problem to approximate.