Internal 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.
• Hardness: APX-hard. [69]
• Approx.: Approximable within approximation ratio $2 \rho$ on metric instances, where $\rho$ is the the approximation ratio for the Steiner Tree Problem. [107]
• Comment: Approximable within approximation ratio $\frac{9}{7}$ on instances where edge weights are restricted to 1 and 2. [70]