An Upper Bound of the Complexity of Maximum Flow

This post is part of a series of algorithm notes originally intended only for myself. If you find yourself lacking some background knowledge while reading, that’s completely normal — these notes were never meant to be a comprehensive introduction. I won’t go into all the prerequisites here. Nevertheless, I hope these notes can still provide some inspiration, even if the details are sometimes a bit sketchy.

We prove that the time complexity of the Edmonds-Karp algorithm for maximum flow problem is $O(|V||E|^2)$, i.e., the number of iterations is $O(|V||E|)$.

Let $s,t$ respectively denote the source and sink vertex. Let $\dist_f(v)$ denote the shortest distance from $s$ to $v$ in the residual network $G^f$. Let $P(v,f)$ denote a shortest path from $s$ to $v$ in $G^f$.

Step 1. $\dist_f(v)$ is nondecreasing.

Assume that $\dist_{f’}(v)<\dist_f(v)$ for some iteration $f\to f’$. Then $P(v,f’)$ must contain new reverse edges generated by this iteration. Let $(u,w)$ be the first new reverse edge in $P(v,f’)$. Then $P(u,f’)$ contains no new reverse edges. By properties of BFS, we can let $P(u,f’):= P(u,f)$. Note that the second last vertex of $P(u,f)$ is $w$ because $(u,w)$ is a new reverse edge. Now $P(v,f’)$ contains both $(w,u)$ (in $P(u,f’)=P(u,f)$) and $(u,w)$, a contradiction.

Step 2. After $(u,v)$ acts as a bottleneck, $\dist_f(u)$ increases by at least $2$ before $(u,v)$ becomes a bottleneck again.

After $(u,v)$ acts as a bottleneck (suppose during iteration $f\to*$), its reverse edge must be used (suppose during $f’\to*$) before it can become a bottleneck (be used) again (suppose during iteration $f’'\to*$). By properties of BFS,

\[\begin{cases} \dist_f(v)=\dist_f(u)+1\\ \dist_{f'}(u)=\dist_{f'}(v)+1\\ \dist_f(v)\leq\dist_{f'}(v) \end{cases}\implies\dist_{f''}(u)\geq\dist_{f'}(u)\geq\dist_f(u)+2.\]

Step 3.

During each iteration, at least one edge acts as a bottleneck. $\dist$ can increase by no more than $O(|V|)$ (from $0$ to $|V|-1$). Hence each edge can serve as a bottleneck for at most $O(|V|)/2$ times. That leads to the desired upper bound of the number of iterations. Q.E.D.