Packing Directed Node-Disjoint Steiner Trees

• INSTANCE: Directed multigraph $G=(V,E)$ , set of terminals $S\subseteq V$ , root $r \in V$ .
• SOLUTION: A set $\mathcal{T} = \{T_1 , ... , T_m \}$ of directed Steiner trees $T_i$ for $S$ rooted at $r$ in $G$ with pairwise disjoint sets of Steiner nodes.
• OBJECTIVE: Maximize.
• Approx.: Approximable within approximation ratio $O(m^{1/2+ \epsilon})$ , where m denotes the number of edges[34].
• Hardness: NP- hard to approximate within $m^{1/3-\epsilon}$ [34].