In this paper, we study a survivable network design problem on directed graphs, 2-Connected Directed Steiner Tree (2-DST): given an @math -vertex weighted directed graph, a root @math , and a set of @math terminals @math , find a min-cost subgraph @math that has two edge vertex disjoint paths from @math to any @math . 2-DST is a natural generalization of the classical Directed Steiner Tree problem (DST), where we have an additional requirement that the network must tolerate one failure. No non-trivial approximation is known for 2-DST. This was left as an open problem by , [SODA'09; JCSS] and has then been studied by [SODA'12; TALG] and Laekhanukit SODA'14]. However, no positive result was known except for the special case of a @math -shallow instance [Laekhanukit, ICALP'16]. We present an @math approximation algorithm for 2-DST that runs in time @math , for any @math . This implies a polynomial-time @math approximation for any constant @math , and a poly-logarithmic approximation running in quasi-polynomial time. We remark that this is essentially the best-known even for the classical DST, and the latter problem is @math -hard to approximate [Halperin and Krauthgamer, STOC'03]. As a by product, we obtain an algorithm with the same approximation guarantee for the @math -Connected Directed Steiner Subgraph problem, where the goal is to find a min-cost subgraph such that every pair of terminals are @math -edge vertex connected.
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 i1, 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=logk, we obtain an O(log2k) 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. Given an acyclic directed network, a subsetS of nodes (terminals), and a rootr, theacyclic directed Steiner tree problem requires a minimum-cost subnetwork which contains paths fromr to each terminal. It is known that unlessNP⊆DTIME[npolylogn] no polynomial-time algorithm can guarantee better than (lnk) 4-approximation, wherek is the number of terminals. In this paper we give anO(kź)-approximation algorithm for any ź>0. This result improves the previously knownk-approximation.