Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Suppose a network $N = (G,c,s,t)$ where $c$ is real.

How do you find all min-cuts? (or how do you find the cut with the least number of vertices)

I've tried messing with the capacity, but since it might be real I can't get it to work.

EDIT: I'll try to rephrase the question more clearly : Amongst all the $(S,T)$ cuts in $G$ that have minimum capacity, find the one which has the least number of vertices.

(Or, similiarly, how do you find all min$(S,T)$ cuts in $G$ ? )

share|improve this question
    
I am either misunderstanding or you have some confusions regarding cuts. A cut is a partition of the vertices. Therefore the cut with the minimum number of vertices is the empty set or if it must include s, then {s}. You can casually say that you cut the source s from the target t by removing the minimum number of vertices. This is accomplished by expanding each vertex into 2 vertices connected by an edge of cost 1 and you make original edges have cost inf. In this case, I don't know what cost has to do with anything.. Your question also mentions counting min-cuts.. Which one do you intend? –  aelguindy Feb 20 '12 at 17:34
    
@aelguindy I edited the question. Hopefully it's clearer now. –  Shmoopy Feb 20 '12 at 18:02
    
There could be an exponential amount of minimum $(s$-$t)$ cuts in a graph, so if you're hoping that enumerating all minimum $(s$-$t)$ cuts would yield a polynomial-time algorithm to find the one with the fewest number of vertices, you're out of luck. –  Zach Langley Feb 20 '12 at 18:07
1  
@Shmoopy normally one defines the minimum cut to be the cut such that the edges that cross the cut (one vertex on each side) have a minimal sum.. I don't know still what you mean by "minimum number of vertices".. What vertices are you referring to? –  aelguindy Feb 20 '12 at 22:48
1  
@Shmoopy: Do you mean minimum (s,t)-cut, or global minimum cut? (Must the cut separate s and t?) –  JeffE Feb 23 '12 at 19:39

1 Answer 1

The number of partitions A,B which induce a minimum cut is at most $n^2$, and these can be enumerated in time $O(n^2 \log^3 n)$ using the Recursive Contraction Algorithm of Karger and Stein. So it is a simple matter to determine any property you would like of minimum cuts.

share|improve this answer
    
Why are the number of minimum cuts in a graph at most $n^2$? –  Zach Langley Feb 20 '12 at 18:11
1  
The number of cuts can be exponential. Consider the graph consisting of two columns of vertices where each vertex is connected to the one next to it. s is connected to all vertices on the left column, t is connected to those on the right. If each column has n vertices, the graph has $2n + 2$ vertices. If all edges have weight 1, then the number of minimum cuts is $3^{n}$. Which is more than $(2n + 2)^2$ for large enough n. –  aelguindy Feb 20 '12 at 22:53
    
@aelguindy: You're counting minimum (s,t)-cuts; yes, there can be exponentially many. David is counting global minimum cuts, with no fixed terminals s and t; there can be only O(n^2) of these. In your example graph, there are exactly 2n minimum cuts, none of which is an (s,t)-cut. –  JeffE Feb 23 '12 at 19:38
1  
@JeffE that actually explains it. I think the question above is looking for s-t cuts though. –  aelguindy Feb 23 '12 at 21:03

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.