Problem Detail: 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?
Asked By : dspyz
Answered By : D.W.
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).
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).
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/42960
