26
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • 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, 2012 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, 2012 at 13:25
  • $\begingroup$ @Peter: The min cut of the graph. $\endgroup$
    – Jozef
    Sep 2, 2012 at 19:00

4 Answers 4

Reset to default
14
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Is this an approximation algorithm? $\endgroup$
    – Strin
    Dec 10, 2012 at 4:11
  • $\begingroup$ @Strin It's a randomized algorithm that finds the minimum cut with high probability. $\endgroup$
    – Juho
    Dec 10, 2012 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$
    – Sumudu Fernando
    May 12, 2014 at 5:42
8
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ Why doesn't this matter? $\endgroup$
    – The Coding Wombat
    Mar 20, 2019 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$
    – Inuyasha Yagami
    Jan 3, 2021 at 17:48
1
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 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, 2012 at 10:17
0
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.