0
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • $\begingroup$ If the number of vertices is 2, wouldn't you be left with at most one edge? I don't understand why this approach will calculate the min-cut $\endgroup$ – nir shahar Apr 8 at 8:39
1
$\begingroup$

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.

10 repetitions of the contraction procedure in Karger’s algorithm for minimum cut on a 10-vertex graph.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Is krager algorithm always supposed to return the minimum cut ? $\endgroup$ – Amit wadhwa Apr 8 at 14:53
  • $\begingroup$ @Amitwadhwa No, it's a randomized algorithm with a non-zero probability of returning the correct answer. You can boost that probability by running it several times. It's all covered in the Wikipedia article. $\endgroup$ – Pål GD Apr 8 at 15:49

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.