# Calculating a minimum connected subgraph containing a fixed set.

Let $(V,E)$ be a connected, planar graph, and let $S \subset V$ be some desired set of vertices. What is the fastest algorithm, if it exists, to calculate a connected subgraph of $(V,E)$ which contains $S$ and has a minimum number of edges (or, if you like, vertices)? What is its computational complexity?

-

## 1 Answer

I think you are looking at the Steiner tree problem, or something very similar. There's a huge literature and the wikipedia page seems to be as good a place to start as any. Note that it's NP hard.

-