How can I find the minimum cut on a graph using a maximum flow algorithm?
I need to find the minimum cut on a graph. I've been reading about flow networks, but all I can find are maximum flow algorithms such as Ford-Fulkerson, push-relabel, etc. Given the max flow-min cut theorem, is it possible to use one of those algorithms to find the minimum cut on a graph using a maximum flow algorithm? How?
The best information I have found so far is that if I find "saturated" edges i.e. edges where flow equals capacity, those edges correspond to the minimum cut. Is that true? It doesn't sound 100% right to me. It is true that all edges on the minimum cut will be saturated, but I believe there might also be saturated edges which are out of the minimum cut "path".
Answer
From the source vertex, do a depth-first search along edges in the residual network (i.e., non-saturated edges and back edges of edges that have flow), and mark all vertices that can be reached this way. The cut consists of all edges that go from a marked to an unmarked vertex. Clearly, those edges are saturated and thus were not traversed. As you noted, there might be other saturated edges that are not part of the minimum cut.