2
$\begingroup$

This algorithm runs natively in O(V * E^2).

The description states that

The running time of O(V * E^2) is found by showing that each augmenting path can be found in O(E) time, that every time at least one of the E edges becomes saturated (an edge which has the maximum possible flow), [...]

My graph has the property that at there are exactly |V| edges with a limited capacity, that is, all remaining |E|-|V| edges have an unlimited capacity; any amount of flow can pass through them.

Given that those edges with an unlimited capacity can never become saturated, can I safely assume that a maximum of |V| augmenting paths will be found, and therefore the complexity reduced to O(V * E)?

If so, is there an adequat proof for the assumption made in the Wiki article? It only states There is an accessible proof in Introduction to Algorithms.

$\endgroup$
5
$\begingroup$

Edmonds-Karp algorithm works by building successive flows $f_0, \dots, f_n$ where each flow $f_{i+1}$ can be obtained by combining $f_i$ and a path in the "residual graph" $G_{f_i}$ obtained through a BFS (the residual graph is just the original graph where we removed full edges).

Now, the idea of the proof in Introduction to Algorithms is to introduce a distance $\delta_f(s,v)$ from the source node $s$ to all nodes $v\in V$ in the graph $G_f$. Then they prove 4 things:

  • $\delta_{f_i}(s,v)$ can only increase with $i$ (i.e. $\delta_{f_i}(s,v)\leq \delta_{f_{i+1}}(s,v)$) that is their lemma 26.7;

  • if an edge $(u,v)$ is not saturated by a flow $f_i$ (i.e. $(u,v)$ is not saturated in $f_{i-1}$ but is in $f_i$) and then unsaturated in the flow $f_j$ with $j>i$ then $\delta_{f_j}(s,v)-\delta_{f_i}(s,v)\geq 2$. That means an edge can become saturated at most $1+|V|/2$ times (since $\delta_{f}(s,v)\leq|V|$);

  • at each BFS, an edge become saturated.

By combining these, we have that each edge can be saturated at most |V|/2+1 times ($\delta_{f}(s,v)\leq |V|$) and that the Edmonds-Karp algorithm is in $O(E×(E×V))$ where $O(E)$ is the time taken for one BFS and $O(E×V)$ the number of BFS (i.e. the maximum number of times an edge can become saturated).

For you the complexity is O(K×V×E) : finding a path is in $O(E)$ and you might have to find $(|V|/2+1)×K$ times an augmenting path where $K$ is the number of edges that can become saturated (i.e. $K=V$ for you thus $O(E×V^2)$).

$\endgroup$
  • 1
    $\begingroup$ Awesome. Welcome to the site! $\endgroup$ – David Richerby Mar 27 '17 at 19:56
  • $\begingroup$ @Louis Actually, I just noticed that in Edmonds-Karp, there is a back edge for every edge, even the ones with infinite capacity. The initial capacity of those back edges is 0, so the complexity should still be O(E^2*V), right? $\endgroup$ – Robert Hönig Apr 12 '17 at 17:40
  • $\begingroup$ Yes. If you have to add "back" edges with 0 capacity then they count in the K. So the complexity might go back to $O(E^2 \times V)$. But, note that you don't have to always add back edges, you only need to add a back edge $(v,u)$ for the edge $(u,v)$ if there are not already a $(v,u)$. If the infinite capacity goes both way then, you are good to go. $\endgroup$ – Louis Apr 13 '17 at 21:47

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.