Which min-cut does the Ford-Fulkerson algorithm find?

Question

There can be multiple min-cuts in a network. E.g:

has four min-cuts and Ford-Fulkerson finds the one "nearer" to s (the source). Can we say the same for all networks? That is, Ford-Fulkerson finds the cut nearest to the source? If true, how do we formalize the concept of "nearest to the source" in flow networks?

Reliable

have you find the answer? I want to hear the answer. Having same thought :) – Chiastolite

Answer 1

Let's represent a cut as a set of vertices that contains the source but not the sink. Minimum cuts have the property that the intersection of two minimum cuts is a minimum cut (this is true for unions also). Thus, the intersection of all minimum cuts is in a sense the minimum cut "nearest" to the source, because it is a subset of every other minimum cut.

United

Answer 2

(Assume that the fact that min cuts are closed under intersection.)

We claim that the intersection of min cuts (closest cut), is exactly the cut returned by FF. Here's a rough sketch of a proof.

From MaxFlow MinCut Theorem, the following result is established:

a cut is minimum iff every edge leaving it is fully saturated, i.e. f(e) = c(e).

So, for contradiction assume there is a min cut C = Ca, Cb which is closer to the source than the one returned by FF, which I will call F = Fa, Fb.

Then take the edge e = (v, w) such that it was in Fa but now is not in Ca (it is an outgoing edge of Ca). This edge must be fully saturated. So by def of residual graph there would be only backwards edge (w, v) in the residual graph and then that node w would be unreachable - yet w was in Fa, so it must have been reachable, a contradiction.

Zapateado