Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question
1  
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 '12 at 13:14
    
Are you trying to find the min-cut for given source and sink nodes or the min-cut of the graph? –  Peter Sep 2 '12 at 13:25
    
@Peter: The min cut of the graph. –  Jozef Sep 2 '12 at 19:00
add comment

3 Answers 3

up vote 7 down vote accepted

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.

share|improve this answer
    
Is this an approximation algorithm? –  Strin Dec 10 '12 at 4:11
    
@Strin It's a randomized algorithm that finds the minimum cut with high probability. –  Juho Dec 10 '12 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. –  Sumudu Fernando May 12 at 5:42
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
    
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. –  Paresh Dec 10 '12 at 10:17
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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