- INSTANCE: Graph , edge costs , a set of terminals.
- SOLUTION: A Steiner tree for in such that contains at most branching nodes.
- COST FUNCTION:
- OBJECTIVE: Minimize.
*Approx.:*For being constant, solvable in polynomial time when the input graph is acyclic or when is also fixed and the input graph is of bounded treewidth [106]*Hardness:*NP-hard to approximate within for every when is not fixed, even in planar graphs with unit edge costs [106]

2015-04-27 Revision: 288 PDF version