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