### typedeftemplate's blog

By typedeftemplate, history, 4 weeks ago,

Hi all,

While learning about minimum spanning trees a while back, I encountered the following problem:

Given a connected undirected graph $G = (V, E)$ and a subset of vertices $S = {v_1, v_2, \ldots, v_n}$, find a forest in which each vertex $v \in V \setminus S$ is connected to exactly one vertex of $S$ such that this forest has minimum total length (sum of edge weights).

I vaguely remember that the solution to this problem involved reducing the problem to a minimum spanning tree problem. In particular, a graph $G'$ was constructed in which one could run the minimum spanning tree on $G'$ in order to retrieve the final answer. However, I've forgotten the solution, and I'm wondering if someone can explain the solution to me.

I think that one can just keep edges of the form $(u, v)$ where $u$ is in $S$ and $v$ isn't. From here, I think we can just run an MST algorithm on the graph $G'$, but I'm not entirely sure if this is correct.

Thanks

• +2

 » 4 weeks ago, # |   0 Auto comment: topic has been updated by typedeftemplate (previous revision, new revision, compare).
 » 4 weeks ago, # |   +13 Before running Kruskal's algorithm, join vertices $v_1,\ldots,v_n$ in the union-find data structure.
•  » » 12 days ago, # ^ |   -6 Can you explain more.
 » 4 weeks ago, # | ← Rev. 2 →   0 Imagine there is an invisible node $P$ connected with $v_1,v_2,...,v_n$ already, then you can do any sort of MST algo.If you use Kruskal, you just have to merge $v_1,v_2,...,v_n$ in the union data structure as they are already connected together with $P$.If you use Prim, you should put $v_1,v_2,...,v_n$ in the queue and set them as connected to the main part of the tree.
 » 12 days ago, # |   -6 wow!What a technique to find solution of codechef long challenge question.....Bro u just modified the question excellently in the way u wanted....
 » 12 days ago, # |   -6 Getting the vibe of D-Dimensional MST of long challenge ;)