k-Steiner Forest Problem

• INSTANCE: Graph $G=(V,E)$ , cost function $c : E \rightarrow {\mathbb{R}}_+$ , set of demands $D=\{ (s_{1},t_{1}),..., (s_{l},t_{l})\}$ , integer $k\leq l$
• SOLUTION: A forest $F$ in $G$ such that at least $k$ pairs from $D$ are connected by $F$ .
• COST FUNCTION: $\sum_{e \in F} c_{e}$ .
• OBJECTIVE: Minimize.
• Approx.: Approximable within $O(min \{n^{2/3}, \sqrt{l} \} \log k)$ [111].
• Hardness: NP-hard.