1
$\begingroup$

In a network flow graph, using the Ford–Fulkerson algorithm, we can find a residual graph G_f which no augmenting paths. This gives us a way of finding one minimum cut (a cut (S, T) with minimum capacity) where S is the set of vertices reachable from the source vertex s in G_f (and it is clear that this set of vertices are not in T, the cut that is on the side of the sink vertex t).

Analogously, we can repeat the Ford–Fulkerson algorithm to find a residual graph G'_f that is anchored at the sink t, such that we can find another minimum cut (S', T') where T' is the set of vertices reachable from the sink vertex t in G'_f. It is possible that (S, T) and (S', T') are different (see my made-up network flow below with 2 different minimum cuts):

enter image description here

The question there is, is there are more comprehensive way of finding other minimum cuts in the the flow network? Or are there only ever a maximum of 2 minimum cuts in a flow network?

$\endgroup$
1
  • $\begingroup$ In the above link, I have added a simple example of a flow network that contains an exponential number of min-cuts. $\endgroup$ Commented May 14, 2021 at 13:46

0

Browse other questions tagged or ask your own question.