8
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • $\begingroup$ Is there a quick reference for the definition of a sparse s-t flow? $\endgroup$
    – chazisop
    Apr 17, 2013 at 7:41
  • $\begingroup$ 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 $\endgroup$
    – Jinggang
    Jun 5, 2017 at 7:38

2 Answers 2

Reset to default
8
$\begingroup$

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.

Improve this answer
$\endgroup$
-1
$\begingroup$

Is there a quick reference for the definition of a sparse s-t flow?

In the general case, having the max-flow it is quite easy to determine the min-cut, via the max-flow , min-cut theorem. The edges that are fully saturated form a cut set, so by selecting one vertex for each such edge, one can form a min-cut. Trivially, this is O(m) in the worst case, and also if one makes the running time output-sensitive, then the number of edges in the flow or even better, the number of saturated edges in the flow, always is an upper bound on the running time of the algorithm for finding the min-cut from the max-flow. So if you have a modification that finds those sparse s-t flows in linear time in the size of the flow, finding the min-cut won't change the algorithm's runtime asymptotically.

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ I don't have a specific definition. Just something where ford-fulkerson is asymptotically faster than anything else. If all my edges have unit capacity, won't many of them be saturated, including edges that if removed could be easily replaced without impacting the max flow volume? I could remove all these edges and form a cut, but then I'm not sure how I'd replace the ones I didn't actually need to remove. $\endgroup$
    – Elliot JJ
    Apr 17, 2013 at 20:17
  • $\begingroup$ It depends on the graph. If you had unit capacities and a dense graph, it's quite likely that you would have many flows with max-value, this in turn could be interpreted as that you could have a large number of different min-cuts as well. Have a look also at this reference: en.wikipedia.org/wiki/Max-flow_min-cut_theorem $\endgroup$
    – chazisop
    Apr 18, 2013 at 11:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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