# 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

In their solution they prove that an edge can be critical at most V/2 times, and that means that there are at most EV augmenting paths because every augmenting path contains at least one critical edge, meaning that the number of augmenting paths is less than the number of critical edges.

You have proven that the sum of the number of times an edge containing vertex v, for all vertices v is at most V^2, but that does not imply that the number of augmenting paths is at most V^2.

you want to exploit the fact that not only that every edge is critical at most V/2 times, but all the edges leaving a certain vertex together are critical at most V/2 times, which is useless in the case when every out degree is 1

-
well, I think I proved that the number of times an edge becomes critical, over all edges emanating from a vertex v, is at most indegree(v) + outdegree(v) + |V|/2. So the total number of times any edge in the graph becomes critical is at most 2E+V^2/2. so shouldn't that bound the number of augmenting paths? –  SorcererofDM Jan 8 '13 at 0:42
the number of augmenting paths is that, times the number of edges, since an augmenting path, although containing many edges, may contain only one critical edge. –  Bojan Serafimov Jan 8 '13 at 1:04
as you said, "the total number of times any edge in the graph becomes critical is at most 2E+V^2/2" that is O(V^2). The total number of times ALL edges becomes critical is at most O(EV^2). That is worse than their solution. –  Bojan Serafimov Jan 8 '13 at 1:13
I'm not sure if this is what you were talking about, but I have finally 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. –  SorcererofDM Jan 8 '13 at 1:23
mmm, I'm not sure how to mark this question as answered, but if you want, mods, you can close this thread. –  SorcererofDM Jan 8 '13 at 1:27
show 1 more comment