1
$\begingroup$

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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

Hint: Add a new vertex to your graph..

Further hint:

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

Improve this answer
$\endgroup$
4
  • $\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, 2020 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$
    – Elle Najt
    Sep 22, 2020 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, 2020 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$
    – Elle Najt
    Sep 22, 2020 at 7:44

Your Answer

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