5
$\begingroup$

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

  • 0
    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?2012-02-20
  • 0
    @aelguindy I edited the question. Hopefully it's clearer now.2012-02-20
  • 0
    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.2012-02-20
  • 0
    @ZachLangley I think the idea is to use the min cut max flow theorem but I cant figure out how.2012-02-20
  • 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?2012-02-20
  • 1
    @Shmoopy: Do you mean minimum (s,t)-cut, or global minimum cut? (Must the cut separate s and t?)2012-02-23
  • 0
    minimum {s,t}-cut yes..2012-02-27
  • 0
    I wonder whether the question is, among all minimum capacity cuts $(S,T)$ that separate source from sink, find one that minimizes the number of *edges* in the network that go from $S$ to $T$.2012-09-03

1 Answers 1

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.

  • 0
    Why are the number of minimum cuts in a graph at most $n^2$?2012-02-20
  • 2
    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.2012-02-20
  • 0
    @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.2012-02-23
  • 2
    @JeffE that actually explains it. I think the question above is looking for s-t cuts though.2012-02-23