Directed Steiner Tree Problem

• INSTANCE: Directed graph $G=(V,E)$ , edge costs $w:E \rightarrow \mathbb{R}^+$ , root $r \in V$ , set of terminals $S\subseteq V$ of size $(\vert S\vert=k)$ .
• SOLUTION: A directed tree $T=(V_{T}, E_{T})$ in G rooted at $r$ such that $S \subseteq V_{T} \subseteq V$ , $E_{T} \subseteq E$ .
• COST FUNCTION: $\sum_{e \in E_{T} } w(e)$ .
• OBJECTIVE: Minimize.
• Approx.: Approximable within approximation ratio $O(\vert S\vert^{\epsilon})$ for every $\epsilon >0$ [27].
• Hardness: For every fixed $\epsilon >0$ cannot be approximated within ratio $\log^{2\textbf{-}\epsilon}n$ , unless $NP\subseteq ZTIME(n^{polylog(n)})$ [61].
  
• Comment: Admits a $O(l^{3}t^{2/l})$ -approximation algorithm with running time $O(t^{2l}n^{l})$ , for any integer $l \leq n$ , where t is the number of terminals. This gives a $O(t^{\epsilon}/\epsilon^{3})$ -approximation algorithm with running time $O(t^{4/\epsilon}/n^{2/\epsilon})$ for any fixed $\epsilon >0$ , and an $O(\log^{t})$ -approximation in quasi-polynomial time [109], [79], [80], [60].