I am trying to understand the proposed "Randomized Linear-Time Algorithm to Find MST".

My findings: I have read and search almost every available resource( main paper, wiki, reports on paper, lecture on paper ) but not getting any clue regarding my confusion.

Question: In the original paper Section 3: The Algorithm "Step 2" says "In the contracted graph, choose a subgraph H by selecting each edge independently with probability 1/2."

If I have 6 vertexes with 14 edges. And if I choose 7 edges with probability 1/2 then there might be some isolated vertex. In that case, what will happen to that isolated vertex?

  • 1
    $\begingroup$ What do you mean by "choose 7 edges with probability 1/2"? You choose each edge with probability 1/2. You might choose 0 edges or 14 edges. The probability to choose exactly 7 edges is only 21%. $\endgroup$ – Yuval Filmus Dec 4 '17 at 8:52
  • $\begingroup$ I have lack knowledge of probability. So, I misinterpret that part. Let me rephrase what I understood. "Choosing anything with probability 1/2 means, either I will choose it, or I will not choose it. And chances of choosing it 1/2 also chances of not choosing it 1/2." In other cases, if it says "Choosing anything with probability 1/4 means, either I will choose it, or I will not choose it. And chances of choosing it 1/4 and chances of not choosing it 3/4." Please let me know if I am correct. $\endgroup$ – Choudhury A. M. Dec 4 '17 at 13:45
  • 1
    $\begingroup$ It is impossible to understand randomized algorithms without a good grasp of elementary probability theory. I suggest you learn enough probability to be able to calculate the probability that exactly 7 edges are chosen, and only then proceed in your efforts to understand this particular algorithm. $\endgroup$ – Yuval Filmus Dec 4 '17 at 14:03

Nothing in particular happens if there is an isolated vertex. The algorithm is correct even if $H$ consists of no edges, or if it consists of all edges. The algorithm proceeds by finding a minimum spanning forest on $H$, and using it to prune the contracted graph. IF $H$ consists of no edges, then nothing is pruned, but the algorithm remains correct - this only affects the running time.

Note also that the algorithm is for the more general minimum spanning forest problem. Hence there is absolutely no problem if the graph is not connected. The algorithm will find a minimum spanning tree in each connected component.

| cite | improve this answer | |

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.