After running a max flow algorithm, find in a flow network all edges that are in some min-cut

user_11790637 0
Viewed 348

Let G=(V,A,s,t,U) be a flow network. Suppose we have obtained a max flow. Is there a fast algorithm to find all edges that are in some min-cut?

I know that if x is a max flow, then we can find in the residual network G(x) the set S of vertices reachable from the source s, and T the set of vertices from which we can reach t. And consequently, S and its complement is a min-cut. Moreover, T and its complement also form a min-cut.

If, unfortunately, it happens that T is not the complement of S, then the min-cut is not unique. And I am wondering whether there is a good way to determine whether the edges whose ends lie in neither S nor T belong to a min-cut or not.

network-flow graph algorithm
1 Answers

Each arc u-->v belongs to some s--t min cut if and only if

  1. there is no residual path from u to t,
  2. there is no residual path from s to v, and
  3. there is no residual path from u to v.

To prove the if direction, consider the cut consisting of vertices reachable from s or u by a residual path, which is an s--t cut by (1), has zero residual capacity and hence is an s--t min cut by construction, and contains u-->v by (2) and (3).

To prove the only if direction, we can use an s--t min cut that contains u-->v to show that, for every path from u to t, from s to v, or from u to v, some arc in the path is non-residual.

This gets you to O(n m) time fairly easily. Maybe that's good enough -- if it isn't, there is a literature on answering offline reachability queries that might be useful.

user_21446690
Related