Advanced Algorithm Q.33

33Consider the input graph G as given below. Assume that we contract uniformly at random the edges of G until only two vertices remain. Which of the following statements are true?

A
The probability that the randomized algorithm returns a mincut is greater than 1/100
B
The probability that the randomized algorithm returns a mincut is less than 1/8
C
For any choice of the first edge to contract, there is a non zero probability that randomized algorithm returns the correct answer

Option : B
Explanation : Option A and B both are correct.

Forgot your password?

I agree with the Terms.