Node Weighted Steiner Network

• INSTANCE: Graph $G=(V,E)$ , node weights $w\colon V\to \mathbb{R}^+$ , edge costs $c\colon E\to \mathbb{R}^+$ , $k$ terminal sets $R_1,\ldots , R_k\subseteq V$
• SOLUTION: A forest $F=(V_F,E_F)$ in $G$ such that each $R_i$ is contained in a connected component of $F$
• COST FUNCTION: $\sum_{v\in V_F}w(v) +\sum_{e\in E_F}c(e)$
• OBJECTIVE: Minimize
• Approx.: Approximable within approximation ratio $O(\log k)$ [76]
• Hardness: NP-hard to approximate within $(1-\epsilon )\ln (k)$ for every $\epsilon >0$ [54].