# Finding the minimum cut of an undirected graph

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?

• 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.)
– Raphael
Sep 2, 2012 at 13:14
• Are you trying to find the min-cut for given source and sink nodes or the min-cut of the graph? Sep 2, 2012 at 13:25
• @Peter: The min cut of the graph. Sep 2, 2012 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.

• Is this an approximation algorithm? Dec 10, 2012 at 4:11
• @Strin It's a randomized algorithm that finds the minimum cut with high probability.
– Juho
Dec 10, 2012 at 17:42
• 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. May 12, 2014 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.

• Why doesn't this matter? Mar 20, 2019 at 18:09
• 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 :( Jan 3, 2021 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.

• 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. Dec 10, 2012 at 10:17

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

• Welcome! Can you include some details about the algorithm here, to make the answer self-contained? May 29, 2020 at 20:39