Node Weighted Generalized Steiner Tree

• INSTANCE: Graph $G=(V,E)$ , node weight function $w : V \rightarrow \mathbb{R}^+$ , proper function $f\colon P(V)\to\{0,1\}$
• SOLUTION: A subgraph $F=(V_F,E_F)$ of $G$ such that $E_F\cap \delta (S)\geq f(S)$ for all $S\subseteq V$
• COST FUNCTION: $\sum_{v \in V_{F}}w(v)$
• OBJECTIVE: Minimize.
• Approx.: Approximable within approximation ratio $1.6103 \ln k$ [54].
• Hardness: NP-hard to approximate within $(1-\epsilon )\ln (k)$ for every $\epsilon >0$ [54].