Randomized Min-Cut, Karger's Algorithm

Question

I am implementing Karger's algorithm. From what I understand, the number of edges between the final two nodes is not always the Min Cut. What I am having trouble understanding is how do I actually get the min cut from this algorithm. I keep finding a lot of stuff on probabilities, but it all looks like gibberish to me...

From what I have read, I think I need to run Karger's algorithm multiple times on a graph. This will give me a high probability of success of hitting the min cut. I think?...

Can someone please explain this in a simpler way? How do I find the number of times to run this algorithm? Is what I have said above even correct?

Answer 1

Each time you run Karger's algorithm, it will give you a (semi-random) cut. The probability that that cut is the minimum cut is P = 1 / (n^2/2 - n/2), which is much better than just picking a cut completely randomly.

If you run the algorithm once, your probability of getting the min cut is P, but your probability of not getting it is 1 - P. If you run the algorithm twice, then your chances of not getting the min cut is (1 - P) * (1 - P), since you would have to miss the min cut the first time, and the second time.

That's quite a bit better. Running the algorithm twice gives us a higher likelihood of finding the min cut.

If we run the algorithm T times, then the probability of not getting the min cut is (1 - P)^T, which means that the probability of getting the min cut is 1 - (1 - P)^T.

At this point, you ask yourself how badly you want the right solution. Make up some probability (1 in 1,000,000?), and solve for T. That's how many times you should run the algorithm.

It's common to set T = C * (n choose 2) * ln(n), since that gives you less than a (1 / n)^C chance of not finding the min cut, which is a much easier formula to reason about, especially if you set C to 1. Then, you have a lower chance of getting an incorrect cut than you do of randomly picking a single node of your graph. That's pretty good if your graph is big.

In summary, choose C based on how necessary it is to get the right answer. If you don't know how necessary it is, then C = 1 is a good guess, and just run your algorithm (n choose 2) * ln(n) times.

(Most of this math is taken from the wikipedia page. You can find more details there)