- INSTANCE: Graph , set of terminals , steiner nodes , the edge weights , cost function .
- SOLUTION: A tree in such that , and for every
- COST FUNCTION: .
- 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].

2015-04-27 Revision: 288 PDF version