Packing Edge-Disjoint Steiner Trees

• INSTANCE: An undirected multigraph $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$ which have pairwise disjoint sets of edges.
• COST FUNCTION: $\vert\mathcal{T}\vert$
• OBJECTIVE: Maximize.
• Approx.: Approximable within $O(\sqrt{ n} \log{n})$ , where n denotes the number of nodes [34].
• Hardness: Not approximable within $(1-\epsilon)\ln (n)$ unless $NP\subseteq DTIME(n^{\log\log n})$ . APX-hard for four terminals [34].