Maximum Flow

In a graph with flows G = (V, E, C), each edge e has a maximum flow capacity c_e, c_e > 0\,\forall e (think of the train network etc.). We want to find, for a starting vertex s and target vertex t, what's the maximum amount of flow we can achieve in this graph (e.g. maximum amount of goods we can deliver from s to t)

Formally:

\forall v\in V- \{s, t\}\\
\sum_{wv\in E}f_{wv} = \sum_{vz\in E}f_{vz}

Residual Network

For a flow network G=(V, E, C) and flow f_e for each e\in E, the residual network G^f=(V, E^f) is given by:

1. If edge is not saturated: vw \in E and f_{vw} < c_{vw}, then add the edge in to G^f with its remaining capacity c_{vw} - f_{vw}
2. If the edge vw has a positive flow, then add the backward edge wv t G^f with capacity f_{vw}

Ford-Fulkerson

1. Let f_e= 0 for all e\in E
2. Make G^f for current flow f
3. Check if there's any path from s to t, call it \cal P, in G^f. If not, return f.
4. In \cal P, let c(\cal P) be the minimum capacity along \cal P in G^f
5. For each forward edge in \cal P, increase its flow by c(\cal P). For each backward edge, decrease its flow by c(\cal P).

Running Time

A big assumption here is that all capacities are integers. If we have this, we know that the flow always increase by \geq 1 every round.

Let f^* be the maximum flow, then we have at most f^* rounds.

The time per round is the sum of

1. Time to built the residual network: O(V), just copy the vertexes
2. Check st-path: O(V+E) from DFS and BFS
3. Find min capacity: O(V) because worst case scenario we visit every vertex -> V-1 edges
4. Update flows: same as finding min capacity, we just go through each edge in \cal P

\implies Time per round is O(E) \implies Total running time is O(f^*E)

This running time is pseudo-polynomial because it involves f^*.