General Steiner Tree Star Problem

• INSTANCE: Graph $G=(V,E)$ , set of terminals $S\subseteq V$ , steiner nodes $Y \subseteq V$ , the edge weights $c: E \rightarrow \mathbb{R}^+$ , cost function $w: Y \rightarrow\mathbb{R}^+$ .
• 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(v)\leq 1$ for every $v \in V_T\setminus Y$
• COST FUNCTION: $\sum_{e \in E_{T} }c(e)+\sum_{v\in Y \cap V_{T} }w(v)$ .
• OBJECTIVE: Minimize .
• Approx.: Approximable with 5.16 and 5 [75].
• Hardness: Includes the Metric Steiner Tree Problem as a special case, hence it is NP-hard to approximate within an approximation ration 96/95 [36].
• Comment: Special case where S and Y are disjoint is called the Steiner Tree Star Problem. This is already NP-hard [75].