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.
Each arc u-->v
belongs to some s--t
min cut if and only if
u
to t
,s
to v
, andu
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.