Reducing a problem to the MST problem Let $G = (V, E)$ be a connected, undirected graph. Given a subset of distinct vertices $S = \{v_1, v_2, \ldots, v_n\} \subseteq V$, how can I find a forest in which each vertex $v \in V - S$ is connected to exactly one of the vertices of $S$ and is of minimum total length?
This is a problem from an algorithms book that I'm currently struggling with. I'm pretty sure the idea is to construct a graph $G'$ on which a minimum spanning tree algorithm could be used (but I might be wrong). I've thought about it for a while, and I'm not able to make much progress. Could someone please point me in the right direction?
I thought about only keeping edges of the form $(u, v)$ where $u$ is in $S$ and $v$ isn't and running an MST algorithm, but I'm not entirely sure if this is correct.
Thanks
Hint: Add a new vertex to your graph..
Further hint:


...with an edge connecting to each element of $S$.