  In the k-Connected Directed Steiner Tree problem (k-DST), we are given a
directed graph G=(V, E) with edge (or vertex) costs, a root vertex r, a set of
q terminals T, and a connectivity requirement k>0; the goal is to find a
minimum-cost subgraph H of G such that H has k internally disjoint paths from
the root r to each terminal t . The k-DST problem is a natural generalization
of the classical Directed Steiner Tree problem (DST) in the fault-tolerant
setting in which the solution subgraph is required to have an r,t-path, for
every terminal t, even after removing k-1 edges or vertices.
  Despite being a classical problem, there are not many positive results on the
problem, especially for the case k >= 3. In this paper, we will present an
O(log k log q)-approximation algorithm for k-DST when an input graph is
quasi-bipartite, i.e., when there is no edge joining two non-terminal vertices.
To the best of our knowledge, our algorithm is the only known non-trivial
approximation algorithm for k-DST, for k >= 3, that runs in polynomial-time
regardless of the structure of the optimal solution. In addition, our algorithm
is tight for every constant k, due to the hardness result inherited from the
Set Cover problem.

Data Structures and Algorithms