is MST a Steiner tree?

Question

I am a little bit confused about MST and Steiner tree? Is an MST a steiner tree?? and suppose we are given a weighted undirected connected graph G = (V,E) and S ⊆ V is the smallest subtree of an MST of G that contains all the vertices from S a Steiner tree of S in G?

Answer 1

No, here's an example:

\begin{array}{rcl} \blacksquare &\stackrel{2}\leftrightarrow & \blacksquare \\ {\Tiny{1}}\updownarrow& &\updownarrow \Tiny{1} \\ \bullet &\stackrel{1}\leftrightarrow & \bullet \\ \end{array}

The unique minimum weight spanning tree contains the three edges with weight $1$. However, a Steiner tree joining the two black squares uses a single edge for a total weight of $2$ instead of $3$.

I hope this helps $\ddot\smile$

Answer 2

MST and Steiner trees are relatively close concepts since the only difference is that in a Steiner tree you are allowed to add nodes.

However an MST needs not to be a Steiner tree, there are a lot of counterexamples, for example take a equal sided triangle of vertices A,B,C with a fourth vertex D in the middle. Then AB,BC is an MST for A,B,C, however the Steiner-tree AD,BD,CD is smaller.

Concerning your second question, this depends on whether you fix the MST. For a fixed MST, the above is a counterexample. However if you take the smallest subtree out of the subtrees of all MST of subsets of vertices of G then in fact, this is true.

In fact a Steiner tree $T\subset E$ of S is an MST but not of S but of the set $V(T)$ of all vertices belonging to edges in T. So in the above example AD,BD,CD is an MST for A,B,C,D. If a tree T would be a Steiner tree for S, but not an MST for V(T), then there is a smaller MST for V(T), which then in turn would be a smaller Steiner tree for S, which is a contradiction.

Answer 3

Steiner trees can be viewed as a generalization of MST's. A MST must includes all vertices of $V$, whereas a Steiner needs only to include the vertices of a given $S \subseteq V$ (though it can include more than $S$). So it all depends on $S$.

If $S = V$, then indeed a MST is a Steiner tree for $S$. If $S \subset V$, then a MST could be a Steiner tree for $S$, but not necessarily.

As for the second question, that would be too easy - considering MST is polynomial but finding a Steiner tree is NP-Hard. Consider this simple example of $K_3$ with vertices $a,b,c$ and all edge weights to $1$. Take the MST $T$ that consists of the edges $\{ab, bc\}$. Now, say we want to find a Steiner tree for $S = \{a, c\}$. The smallest subtree of $T$ that contains $S$ is actually $T$, of total weight 2. But the Steiner tree for $S$ is just the edge $ac$.