1
$\begingroup$

I was reading the proof of time-complexity for the Edmonds-Karp algorithm here (https://brilliant.org/wiki/edmonds-karp-algorithm/).

Everything in the first part of the proof (The section Monotonically increasing path length) makes sense. However, the last part of it is not very convincing (the part I have highlighted with red).

Can someone convince me that it is true that the fact that "the shortest path increases monotonically in the residual graph" implies a "bound on of one iteration of Edmonds-Karp algorithm to $O(E)$".


enter image description here

$\endgroup$

1 Answer 1

1
$\begingroup$

It is no wonder why that you doubt that "the shortest path increases monotonically in the residual graph" implies a "bound on of one iteration of Edmonds-Karp algorithm to $O(|E|)$".

The time bound of $O(|E|)$ has nothing to do with the fact that "the shortest path increases monotonically in the residual graph".

It takes $O(E)$ time to perform one iteration of Edmonds-Karp algorithm, since what it does is mostly a breadth-first search.

(It takes $O(|V| + |E|)$ time for a breadth-first search on a general graph. However, in the case of finding the maximum flow in a flow network, we assume the given network is connected or there is at least one edge incident to every vertex usually. That is, $|E|\ge |V|-1$ or $2|E|\ge|V|$. Then $O(|V|+|E|)=O(|E|)$)

$\endgroup$
1
  • 1
    $\begingroup$ so in summary, the BFS runs in $O(|V|+|E|)$ time on a general graph, but in a flow network graph it can be proved that BFS runs even faster: $O(|E|)$. In the proof of the edmon-karp time complexity, the author of the proof assumed the reader knew this fact about BFS having a faster running time if "paths are monotonically increasing in a flow network", in that it was common knowledge; therefore he didn't include that information as the explanation for the implication that "paths are monotonically increasing in a flow network" implies "bound on one iteration of Edmonds-Karp algorithm to O(|E|)" $\endgroup$ Commented Aug 11, 2022 at 8:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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