Steiner Tree Problem with Distances 1 and 2

• INSTANCE: Metric space $(V,d)$ , set of terminals $S \subset V$ , such that for all pairs of vertices $u\neq v$ , $d(u,v)\in \{1,2\}$
• SOLUTION: A tree $T=(V_{T}, E_{T})$ such that $S \subseteq V_{T} \subseteq V$
• COST FUNCTION: $d(T):=\sum \limits_{e=\{u,v\}\in E_T} d(u,v)$
• OBJECTIVE: Minimize.
• Approx.: Approximable within approximation ratio 1.25 [11].
• Hardness: APX- hard [87],[13].