Randomized algorithm for minimum cut

Question

Given a simple undirected connected graph $G$, I want to find a min-cut of $G$ using a randomized algorithm.

My attempt was to select a random edge in $G$ and reduce that edge to a single vertex. And recursively do it until the number of vertices is at most 2.

The number of edges present (in the resulting multi-graph) will be the min-cut. This is the standard algorithm I found at many places.

Will this lead to the exact number of min-cut and how can I extract the vertices on each side of the cut?

Answer 1

Yes, that's exactly the correct algorithm, and what you have produced is Karger's algorithm.

Since the algorithm is randomized, you can run it several time over in the hope of getting a better solution. There is no guarantee that you will get the optimum cut, but you can make the error probability as low as you want to.

Here is Thore Husfeldt's illustration of it (cc-by-sa-3.0), 10 repetitions of the contraction procedure in Karger’s algorithm for minimum cut on a 10-vertex graph. The 5th repetition finds the minimum cut of size 3.