2
$\begingroup$

The proof that the Edmonds-Karp algorithm will require at most $O(|V||E|)$ uses the fact that when an augmenting path has critical edge $(u, v)$, $\delta_f(u)$ strictly increases. Therefore, that particular edge can only be critical at most $|V|$ times and the total number of augmenting paths until the max flow is at most $|E| * O(|V|) = O(|V||E|)$.

But consider that vertex $u$ and all its outgoing edges. The sum of the times those outgoing edges are critical must be $O(|V|)$ by a similar reasoning. Couldn't we then take this fact and say the number of augmenting paths will be at most $|V| * O(|V|)$, by summing over the vertices (instead of summing over the edges like the textbook proof)? This would give $O(|V|^2)$ as the bound on the number of augmenting paths.

Put another way, consider the sum $\sum_{v \in v} \delta_f(v)$. This sum is at most $|V|^2$, but is strictly increased after every augmentation, so $O(|V|^2)$ augmentations will be required.

Is there any flaw in this reasoning? We know that $O(|V|^2|E|)$ is possible using Dinic's, but if Edmond's-Karp requires at most $O(|V|^2)$ augmentations we would get this same bound.

I tried searching for this and found this post, but I do not understand the response or comment discussion. Maybe someone can rephrase it?

$\endgroup$
1
$\begingroup$

Here are two papers giving examples that show that the analysis of the Edmonds–Karp algorithm is tight:

$\endgroup$
2
  • $\begingroup$ Is there anything you can point me to that would show why my analysis is incorrect? $\endgroup$ Oct 5 '21 at 13:25
  • 1
    $\begingroup$ You can run your analysis on one of the tight examples and see where it goes wrong. You don’t need us for that. $\endgroup$ Oct 5 '21 at 14:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.