Message No. 134
Updated version of the proof for algorithm Dinitz (is recommended to read)
A brief (but full) central proof for algorithm Dinitz is as follows (to be read carefully word by word (מילה מילה) ):

Statement: The length of the layered network strictly increases from phase to phase.

Proof: Consider some phase (henceforth called "current phase"). At its beginning, we built a layered network L_f of length l in the residual network N_f. The stopping condition of the phase is that there is no path from s to t in the updated layered network. Denote by f' the flow when the current phase stops. In order to prove the statement, it is sufficient to show that the residual network N_f' contains no path from s to t of length at most l. Let us prove that.

Notation: For any vertex v, we denote by d0(v) the layer number of v in L_f. (Important: Since layers are never changed during the phase, also d0(v) is fixed during the phase!) We say formally that an edge (u,v) "increases d0" by d0(v) - d0(u). We call (u,v) a jumping edge if it increases d0 by at least 2 (that is if d0(v) >= d0(u) + 2).

First of all, let us investigate the residual network N_f' (with no relation to paths in it).

Lemma 1: There is no jumping edge in residual network N_f'.

Proof. In N_f', there are old edges, inherited from N_f, and new edges, added during the phase. There is no jumping edge in N_f, by the property of BFS. Pay attention that any new edge (v,u) added to the residual network after some iteration is opposite to an edge (u,v) of the augmenting path of that iteration. Since (u,v) increases d0 by 1 (by the algorithm), edge (v,u) decreases d0 by 1. Hence also no new edge in N_f' is a jumping edge.

Now, let us consider an arbitrary path P from s to t in N_f'.

Lemma 2: a) The length of P is at least l. b) The length of P equals l only if P belongs entirely to the layered network L_f.

Proof: Pay attention that all edges of P together increase the layer number from 0 (d0(s)) to l (d0(t)).

a) Assume |P|<l. Since there are less edges than the total increase of d0, there exists an edge in P which increases d0 by at least 2, a contradiction to Lemma 1.

b) Assume |P| equals l. By the same reasons, every edge in P should increase d0 by exactly 1. Indeed, if some edge of P does not increase d0, then the remaining l-1 edges increase d0 together by at least l, and we continue as in item a. Pay attention that edges increasing d0 by 1 are old edges only, since any new edge decreases d0 by 1. By the definition of L_f, this implies that any edge in P is in L_f, as required.

Proof of the main statement: By Lemma 2, the only case of |P| =< l is when P is included in L_f. Since P is a path in N_f', all edges of P are not saturated by f', by the definition of N_f'. In other words, the updated layered network L_f still contains a path from s to t, a contradiction to the assumed stopping condition of the current phase.

published on 24/08/2014 14:26:52 by Yefim Dinitz