Packing Steiner Forest

• INSTANCE: Undirected multigraph $G=(V,E)$ , set ${\mathcal S}=\{S_1,...,S_t\}$ of pairwise disjoint subsets $S_i$ of $V$

• SOLUTION: A set ${\mathcal F}$ of pairwise edge-disjoint Steiner forests $F_i$ for ${\mathcal S}$ in $G$

• COST FUNCTION: $\vert{\mathcal F}\vert$ (the number of Steiner forests)

• OBJECTIVE: Maximize.

• Approx.: APX [81].

• Hardness: NP-hard.

• Comment: If each $S_i$ is $Qk$ -edge-connected in $G$ , then there are $k$ edge-disjoint $S$ -forests in $G$ . The best upper bound achieved on $Q$ is 32. This yields the first polynomial time constant factor approximation algorithm for the Steiner Forest Packing problem. [81]