  We consider the k-outconnected directed Steiner tree problem (k-DST). Given a
directed edge-weighted graph $G=(V,E,w)$, where $V=\{r\}\cup S \cup T$, and an
integer $k$, the goal is to find a minimum cost subgraph of $G$ in which there
are $k$ edge-disjoint $rt$-paths for every terminal $t\in T$. The problem is
know to be NP-hard. Furthermore, the question on whether a polynomial time,
subpolynomial approximation algorithm exists for $k$-DST was answered
negatively by Grandoni et al. (2018), by proving an approximation hardness of
$\Omega (|T|/\log |T|)$ under $NP\neq ZPP$. Inspired by modern day
applications, we focus on developing efficient algorithms for $k$-DST in graphs
where terminals have out-degree $0$, and furthermore constitute the vast
majority in the graph. We provide the first approximation algorithm for $k$-DST
on such graphs, in which the approximation ratio depends (primarily) on the
size of $S$. We present a randomized algorithm that finds a solution of weight
at most $\mathcal O(k|S|\log |T|)$ times the optimal weight, and with high
probability runs in polynomial time.
