Steiner Forest Problem

• INSTANCE: Graph $G=(V,E)$ , cost function $c : E \rightarrow {\mathbb{R}}_+$ , set of $k$ terminal pairs $S= \{(s_{1},t_{1}),..., (s_{k},t_{k})\}$ .
• SOLUTION: A forest $F\subseteq E$ such that for all $1\leq j\leq k$ , vertices $s_j$ and $t_j$ are contained in the same connected component of $F$
• COST FUNCTION: $\sum_{e \in F} c_{e}$ .
• OBJECTIVE: Minimize.
• Approx.: Approximable within $2-1\slash k$ [3].
• Hardness: NP-hard to approximate within 96/95 [36].
• Comment: When $G$ is a planar graph [9] obtained a PTAS.