6
$\begingroup$

When using Ford-Fulkerson to find max-flow between s and t, the exact choice of flow-graph depends on which paths are found.

However, if you then use the left-over residual graph to produce a min-cut (by flood-filling outward from s along any edges or reverse edges with left-over capacity), it seems the same cut is obtained regardless of which flow-graph you use.

Is this true?

Is there a way to iterate over all cuts such that each iterator-step requires only polynomial time?

$\endgroup$
5
$\begingroup$

Yes, Ford-Fulkerson always finds the cut that is "closest" to the source. See this question for a formalization of what is meant by "closest".

A graph can contain exponentially many min-cuts, so beware that any procedure to enumerate all min-cuts must take exponential time in total in the worst case.

Based on what I've read, there are output-sensitive algorithms to enumerate all min $(s,t)$-cuts. After a single maximum flow computation, the running time is $O(n)$ per min-cut that is output. Details can be found in the following paper:

Jean-Claude Picard, Maurice Queyranne. On the structure of all minimum cuts in a network and applications. Combinatorial Optimization II: Mathematical Programming Studies, volume 13, 1980, pp.8--16.
Unfortunately, there does not seem to be a non-paywalled online version of the paper.

(See also here for a related question.)


In contrast, if you want to find all min-cuts of an undirected graph, rather than all min $(s,t)$-cuts, you can use Karger's algorithm to do that efficiently (in polynomial time).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.