Improvement of algorithm due to constrained graph

Question

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.

Answer 1

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