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.



Hint: Add a new vertex to your graph..

Further hint:

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

  • $\begingroup$ 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? $\endgroup$ – user118586 Sep 22 '20 at 7:39
  • $\begingroup$ You need to start the MST algorithm using those edges (or I guess assign them negative weight), but yeah that's the idea. What happens with that MST? Try drawing a picture. $\endgroup$ – Lorenzo Najt Sep 22 '20 at 7:41
  • $\begingroup$ I think I'm starting to get it. Essentially, taking this step "prevents" us from forming a cycle within the set $S$? $\endgroup$ – user118586 Sep 22 '20 at 7:42
  • $\begingroup$ @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$. $\endgroup$ – Lorenzo Najt Sep 22 '20 at 7:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy