<p>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.</p>

<p>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.</p>

<p>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</p>

CC BY-SA 3.0
2013-01-08T00:42:32.913Z
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
CC BY-SA 3.0
2013-01-08T01:04:08.840Z
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
CC BY-SA 3.0
2013-01-08T01:13:50.027Z
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
CC BY-SA 3.0
2013-01-08T01:23:01.803Z
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
CC BY-SA 3.0
2013-01-08T01:27:12.247Z
mmm, I'm not sure how to mark this question as answered, but if you want, mods, you can close this thread.
SorcererofDM
CC BY-SA 3.0
2013-01-08T15:26:51.393Z
I'm new here too, I think this is the way http://meta.stackexchange.com/questions/5234/how-does-accepting-an-answer-work
Bojan Serafimov
CC BY-SA 3.0
2013-01-08T00:16:36.510Z
2013-01-08T00:24:09.033Z
2013-01-08T00:24:09.033Z
Bojan Serafimov
<p>I'm reading CLRS's (Cormen et.a al) <em>Introduction to Algorithm</em>, and arrived at the maximum flow section. It shows that Edmonds-Karp algorithm runs in $O(E^2V)$ time by showing that:</p>

<p>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$.</p>

<p>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 <em>critical</em> 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.</p>

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

<p>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$.</p>

<p>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$. </p>

<p>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.</p>

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

<p>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)</p>

<p>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. </p>

<p>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)$$</p>

<p>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)$.</p>

<p>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.</p>

CC BY-SA 3.0
2013-01-08T00:20:45.173Z
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 [cs.se] which has a broader scope.
Kaveh
CC BY-SA 3.0
2013-01-08T00:37:12.473Z
sorry about that!
SorcererofDM
<graph-theory><graph-algorithms><max-flow>
The existing bound on Edmonds-Karp doesn't seem to be tight
SorcererofDM
# The existing bound on Edmonds-Karp doesn't seem to be tight

(Asked by: username_0 on 2013-01-07)

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.

**Tags:** graph-theory, graph-algorithms, max-flow
> **Comments:**
> **username_1**: 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 [cs.se] which has a broader scope.  
> **username_0**: sorry about that!  

---

## 1 answers

### Answer by username_2 on 2013-01-08. Score: 4

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

> **Comments:**
> **username_0**: 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?  
> **username_2**: 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.  
> **username_2**: 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.  
> **username_0**: 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.  
> **username_0**: mmm, I'm not sure how to mark this question as answered, but if you want, mods, you can close this thread.  
> **username_2**: I'm new here too, I think this is the way http://meta.stackexchange.com/questions/5234/how-does-accepting-an-answer-work  

---

