Introduction to Network Flow Problems
By: Hung Q. Ngo
The augmenting path method
Since the 0-flow is always feasible, one might attempt to gradually increase the flow until the flow gets its maximum value. By definition, in order to increase the flow we have to either increase f(s, v) of an out-edge (s, v) from s or decrease f(v, s) of an in-edge (v, s) to s, as long as the capacity constraint for that edge is still valid. Doing so, however, requires adjusting the flows at edges incident to v so that the flow conservation constraint at v is still valid. In fact, this kind of update shall propagate down to t, which is the place where the conservation constraint does not have to hold. The propagation, as described above, can be done via a “path” from s to t. We make this notion mathematically precise by introducing the notion of a residual network as follows.