Here's a question from a past exam I'm trying to solve:

For an undirected graph $G$ with positive weights $w(e) \geq 0$, I'm trying to find the minimum cut. I don't know other ways of doing that besides using the max-flow min-cut theorem. But the graph is undirected, so how should I direct it? I thought of directing edges on both ends, but then which vertex would be the source and which vertex would be the sink? Or is there another way to find the minimum cut?

  • 1
    $\begingroup$ If you don't have source and target in the original graph, I guess you'll have to try multiple choices. (For any given $s$ and $t$, the minimal cut may not separate the two.) $\endgroup$
    – Raphael
    Sep 2 '12 at 13:14
  • $\begingroup$ Are you trying to find the min-cut for given source and sink nodes or the min-cut of the graph? $\endgroup$
    – Peter
    Sep 2 '12 at 13:25
  • $\begingroup$ @Peter: The min cut of the graph. $\endgroup$
    – Jozef
    Sep 2 '12 at 19:00

There are plenty of algorithms for finding the min-cut of an undirected graph. Karger's algorithm is a simple yet effective randomized algorithm.

In short, the algorithm works by selecting edges uniformly at random and contracting them with self-loops removed. The process halts when there are two nodes remaining, and the two nodes represent a cut. To increase the probability of success, the randomized algorithm is ran several times. While doing the runs, one keeps track of the smallest cut found so far.

See the Wikipedia entry for more details. For perhaps a better introduction, check out the first chapter of Probability and Computing: Randomized Algorithms and Probabilistic Analysis by Michael Mitzenmacher and Eli Upfal.

  • $\begingroup$ Is this an approximation algorithm? $\endgroup$
    – Strin
    Dec 10 '12 at 4:11
  • $\begingroup$ @Strin It's a randomized algorithm that finds the minimum cut with high probability. $\endgroup$
    – Juho
    Dec 10 '12 at 17:42
  • 1
    $\begingroup$ I don't think Karger's is appropriate for finding a cut of minimum weight. The derivation of the probability that it finds a minimum cut is dependent on it finding a minimum-cardinality cut; Karger's is very unlikely to find a minimum cut with many lightweight edges. $\endgroup$ May 12 '14 at 5:42

For every undirected edge $(u,v, weight)$ create two directed edges $(u,v, weight)$ and $(v,u,weight)$.

...but then which vertex would be the source and which vertex would be the sink?

Doesn't matter.

  • 2
    $\begingroup$ Why doesn't this matter? $\endgroup$ Mar 20 '19 at 18:09
  • $\begingroup$ I think we would need to run the max-flow algorithm $|V|$ times. We can fix any one vertex as a source vertex $s$ and then for every other vertex as the sink vertex, we need to run the max-flow algorithm. Therefore, $|V|$ times max-flow. And then, we will take the minimum value cut among all the flow networks which would give the global minimum cut. I do not understand how to obtain the min-cut by running max-flow just once :( $\endgroup$ Jan 3 at 17:48

Ford-Fulkerson algorithm should work for you. You can create two fake vertices viz. the source and sink.

Also have a look at Edmonds-Karp algorithm. There are two variations of it:

  1. One version picks the shortest path
  2. Other picks a path with the maximum capacity

, as opposed to Ford-Fulkerson which picks an arbitrary path.

This is a good resource.

  • 2
    $\begingroup$ Welcome to cs.stackexchange! It might help the OP if you could further explain how the fake vertices are connected to the existing graph. And what will be the edge weights of the new edges. $\endgroup$
    – Paresh
    Dec 10 '12 at 10:17

Check out Stoer-Wagner Algorithm: https://en.wikipedia.org/wiki/Stoer%E2%80%93Wagner_algorithm

  • 2
    $\begingroup$ Welcome! Can you include some details about the algorithm here, to make the answer self-contained? $\endgroup$
    – 6005
    May 29 '20 at 20:39

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.