The Maximal Flow Problem

Suppose we have a graph with nodes labelled and edge capacities . We want to find the maximum flow from to i.e. we want to maximize s.t. and for every : This is a Linear program.

The Ford-Fulkerson Algorithm

First assign some initial flow with value (for example, take ). Then find an augmented path defined on a sequence of nodes

s.t. for every either or . Hence we can change the flow along that augmented path by

Repeat this until there are no more such augmented paths.

This is optimal by the The max-flow min-cut Theorem. To prove there are no more augmented paths, we just need to find a cut with .

Note that the algorithm always terminates for integer (hence also rational) values of (because then ), but might not terminate if there are some irrational values.

Dual problem

Calculate the Lagrangian

Now for and feasible:

• Now pick an optimal solution , and pick: (using notation from The max-flow min-cut Theorem) One can check that Complimentary slackness holds, hence the dual of max-flow problem is indeed the min-cut problem.