# The existing bound on Edmonds-Karp doesn't seem to be tight

I'm reading CLRS's (Cormen et.a al) Introduction to Algorithm, and arrived at the maximum flow section. It shows that Edmonds-Karp algorithm runs in $O(E^2V)$ time by showing that:

1) If we let $\delta_f(s, u)$ be the shortest distance from source $s$ to vertex $u$ in the residual graph after flow $f$ is picked, then CLRS shows that $\delta_f(s, u)$ does not decrease as $f$ gets augmented, for a fixed $u$.

2) Let $c_f(e)$ be the capacity of edge $e$, and $c_f(p)$ the capacity of a path $p$ (the minimum of all $c_f$ on the edges in the path $p$) in the residual graph after flow $f$. If we say that an edge $(u, v)$ in a residual network $G_f$ is critical on an augmenting path $p$ if $c_f(p) = c_f(u, v)$, then CLRS shows that each edge can't become critical more than $|V|/2$ times, and therefore, there can be at most $|E||V|$ augmenting flows, if we sum up this bound over all of the potential $2|E|$ edges in residual graphs.

In particular, CLRS's proof of the 2nd point goes as follows:

If $(u, v)$ becomes critical at $f$, then $\delta_f(s, v) = \delta_f(s, u) + 1$, because we have picked the shortest path from $s$ to $t$.

The next time it becomes critical, there must have been some flow $f'$ that ran through $(v, u)$. Then $\delta_{f'}(s, u) = \delta_{f'}(s, v) + 1$. This must mean $\delta_{f'}(s, u) \ge \delta_f(s, u) + 2$.

Hence every time $(u, v)$ becomes critical after the 1st, $\delta_f(s, u)$ must have increased by 2. As this minimal distance can't exceed $|V|$, each edge can become critical at most $|V|/2$ times. Therefore, there can at most be $O(EV)$ augmenting paths and hence the number of augmentations.

So my comment now comes in as a possible improvement over this proof. Why can't we say the following:

If we augment the edge $(u, v)$ $k$ times,then $\delta_f(s, u)$ increases at least by $2(k-1)$. Now instead of looking at edges, we look at vertices and their degrees. We just need to guarantee the edges going out from any particular vertex $v$ become critical infrequently enough so that $\delta(v)$ doesn't exceed $|V|$ (from now on for convenience I will shorten $\delta_f(s, v)$ to $\delta(v)$). I claim that for any vertex $v$, $\sum_{(v,u)\in E \text{ or } (u, v)\in E} \text{number of times$(v, u)$becomes critical}$ is at most $indegree(v)+outdegree(v)+|V|/2$. (we are looking at "reverse" edges here too because they may appear in the residual graph)

Indeed, the first time any edge becomes critical is "free": it doesn't bump up $\delta(v)$. But for every time after that $\delta(v)$ goes up by 2. So we can get every edge going out from $v$ to become critical once (this is the $indegree(v)+outdegree(v)$ term) and then all other times are bounded by $|V|/2$ for the same reason CLRS writes.

Now if we sum up this bound for all vertices, we get $$\sum_v indegree(v)+outdegree(v)+|V|/2 = 2|E| + |V|^2/2 = O(V^2)$$

This bound is better than the $O(EV)$ bound given by CLRS. Combined with the $O(E+V)=O(E)$ bound for BFS, we find Edmonds-Karp is actually $O(EV^2)$ instead of $O(E^2V)$.

I'm suspicious that I'm missing something, since every where I looked, the bound given for Edmonds-Karp is $O(E^2V)$. So please nitpick away and see where I reasoned incorrectly.

-
Welcome to cstheory, a Q&A site for research-level questions in theoretical computer science (TCS). Your question does not appear to be a research-level question in TCS. Please see the FAQ for more information on what is meant by this. Your question might be suitable for Computer Science which has a broader scope. –  Kaveh Jan 8 '13 at 0:20
sorry about that! –  SorcererofDM Jan 8 '13 at 0:37