Packing Element-Disjoint Steiner Trees on Bounded Terminal Nodes

• INSTANCE: Graph $G=(V,E)$ , set of terminals $S\subseteq V$ .
• SOLUTION: A set $\mathcal{T} = \{T_1 , ... , T_m \}$ of Steiner trees $T_i$ for $S$ in $G$ with pairwise disjoint sets of Steiner nodes.
• COST FUNCTION: $m$ (the number of trees)
• OBJECTIVE: Maximize.
• Approx.: Approximable within $\lceil \frac{\vert S\vert}{2} \rceil\:\:$ [67].
• Hardness: APX-hard even for $\vert S\vert = 3$ [1]. NP-hard to approximate within $O(log\vert V\vert)$ [34].