Directed Steiner Forest (DSF)

• INSTANCE: A directed graph $G=(V,E)$ , an edge cost function $c : E \rightarrow {\mathbb{R}}_+$ , a collection $D \subseteq V \times V$ of ordered node pairs, and an integer $k = \vert D\vert$ .

• SOLUTION: A subgraph $F$ of $G$ that containes an shortest path for (at least) k pairs $(s,t) \in D$ .
• COST FUNCTION: $\sum_{e \in F} c_{e}$ .
• OBJECTIVE: Mininimize.

• Approx.: Approximable within $O(n^{\frac{2}{3} + \epsilon})$ for every $\epsilon >0$ [10].

• Hardness: NP-hard to approximate within $\log (n)^{2-\epsilon}$ .
• Comment: The k-Directed Steiner Forest (k-DSF) is approximable within $O(k^{1/2+\epsilon})$ for every $\epsilon >0$ [47].