# 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

...with an edge connecting to each element of $$S$$.
• Not sure why, but I don't see it. Just to clarify: the suggestion is to add a new vertex $z$ and add $n$ edges of the form $(z, v_i)$? If this is the case, then wouldn't I end up taking all edges of the form $(z, v_i)$ in the MST?
• I think I'm starting to get it. Essentially, taking this step "prevents" us from forming a cycle within the set $S$?
• @dv55 That's a good way to think about it, yes -- or even more, it prevents you from using any edges between different elements of $S$, or between the two sets of nodes connected in the MST to distinct elements of $S$. Sep 22, 2020 at 7:44