Terminal Steiner Tree

• INSTANCE: Graph $G=(V,E)$ , cost function $c: E \rightarrow \mathbb{R}^+ \strut$ , set of terminals $S \subset V$ .
• SOLUTION: A tree $T=(V_{T}, E_{T})$ in $G$ such that $S \subseteq V_{T} \subseteq V$ , $E_{T} \subseteq E$ and $deg_T(s) = 1$ for every $s\in S$ .
• COST FUNCTION: $\sum_{e \in E_{T}}c(e)$ .
• OBJECTIVE: Minimize. be approximated within a factor less than $\log^{2 - \epsilon} \vert S\vert$ . This bound also applies to the node-weighted case. [16]
• Approx.: Approximable within approximation ratio 2.458 on metric instances [33]. Can be improved to 1.9329 using the algorithm presented in [21].
• Comment: For the special case of unit disc graphs, a 20-approximation was given by Biniaz et al. [15]. For the euclidean bottleneck version of this problem, an exact solution can be computed in polynomial time [14].