# Min cut Max flow - Finding the cut with least vertices

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$ ? )

-
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
@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
@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

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.
Why are the number of minimum cuts in a graph at most $n^2$? – Zach Langley Feb 20 '12 at 18:11
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