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 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$.2019-03-19

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.

  • 2
    @JeffE that actually explains it. I think the question above is looking for s-t cuts though.2012-02-23