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

(I have posted the following in theoretical CS stackexchange, but realized that it's the wrong place, so I'm reposting it here)

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.

-

## 1 Answer

I have found the error in my thinking: I thought wrongly that every time after the first that an edge becomes critical, it "adds" at least 2 to the corresponding vertex degree, whereas in reality, there's no such "physical causation" happening; instead, the fact is that every time v's degree increases by 2, it allows edges leaving v to become critical once more. This line of thinking would end up at the same place as CLRS's bound.

-