Steiner Tree Problem

What's difficult is in the middle.

Steiner Tree Problem

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.