Steiner Tree Problem
What's difficult is in the middle.
Shortest Path Problem:
Input: a graph and two nodes
Output: a minimum-cost path between the two nodes
Steiner Tree Problem:
Input: a graph and some nodes
Output: a minimum-cost tree which covers all the input nodes
Minimum Spanning Tree Problem:
Input: a graph
Output: a minimum spanning tree
We can see Steiner tree problem sits in between the shortest path problem and the minimum spanning tree problem. Steiner tree problem does not have a polynomial algorithm unlike the other two problems. What's difficult is in the middle.
