# Fastest way to find an s-t min-cut from an s-t max-flow?

Ford-Fulkerson can find sparse s-t flows in time linear in the size of the flow and number of nodes if the edges have unit capacity.

How could I use a sparse s-t flow to find an s-t min-cut in time proportional to the size of the flow and the number of my nodes, for the sparse/low-volume max-flow case?

• Is there a quick reference for the definition of a sparse s-t flow? – chazisop Apr 17 '13 at 7:41
• 1. Traversing all edges and find saturated edges seemed pretty legitimate intuitively. But one flaw is, not all saturated edges necessarily belong to a min-cut. 2. Min-cut should be a set of edges, not a set of vertices. 3. So the typical solution should just be the accepted answer above. From the max flow network(Either given or you can compute by Ford-Fulkerson or Edmunds-Karp), DFS or BFS from s, mark all vertices that are reachable(The process of trying to find an augmenting path but you know y – Jinggang Jun 5 '17 at 7:38

If you don't use the flow per se, but use the Ford-Fulkerson algorithm (or some version, like Edmonds-Karp), you can get both the max-flow and the min-cut directly as a result. When looking for augmenting paths, you do a traversal, in which you use some form of queue of as-yet-unvisited nodes (in the Edmonds-Karp version, you use BFS, which means a FIFO queue). In the last iteration, you can't reach $t$ from $s$ (this is the termination criterion, after all). At this point, the set of nodes you reached forms the $s$-part of the cut, while the nodes you didn't reach form the $t$-part.
The leaf nodes of your traversal tree form the “fringe” of the $s$-part, while the nodes in your traversal queue form the fringe of the $t$-part, and what you want is the set of edges from the $s$-fringe to the $t$-fringe. This can also easily be maintained during traversal: Just add an edge to the cut when it is examined, and leads to an unvisited node, and remove it if it is traversed (so its target becomes visited). Then, once Ford-Fulkerson is finished, you'll have your min-cut (or, rather, one of them) right there. The running time will be (asymptotically) identical to Ford-Fulkerson (or Edmonds-Karp or whatever version you're using), which should give you what you were looking for.