Max-flow Part III

PDF of Eric’s handwritten notes are here.

Recall Max-flow problem

Given a flow network, find a flow of maximum size.

Recall Ford-Fulkerson algorithm

input: flow network with integer capacities $c_e$ for $e\in E$.

1. Set $f_e=0$ for all $e\in E$
2. Build residual network $G^f$:
• for $\overrightarrow{vw}\in E$:
• if $f_{vw}: add $\overrightarrow{vw}$ with residual capacity $c_{vw}-f_{vw}$
• if $f_{vw}>0$: add $\overrightarrow{wv}$ with residual capacity $f_{vw}$
3. Check for a st-path $P$ in $G^f$
• If such path does not exist, return($f$)
• Otherwise, denote $b=$ minimum residual capacity along $P$ in $G^f$
4. Augment $f$ by $b$ units along $P$
5. Repeat from step 2 until no st-path can be found in $G^f$

Running time:

• Let $C=$ size of max-flow
• The algorithm cost $O(m)$ time per round
• There will be at most $C$ rounds (since the size of flow increases at least by 1 after every round)
• Overall running time is $O(mC)$.

We want the running time to be independent with capacities/size of flows.

Edmonds-Karp algorithm

This algorithm finishes in at most $mn$ rounds and thus reaches overall running time $O(m^2n)$. It also works with any positive capacities (remember that Ford-Fulkerson algorithm requires capacities to be integers).

Edmonds-Karp algorithm is identical to Ford-Fulkerson algorithm except Step 3:

3. Run BFS in $G^f$ and take the path $P$ with fewest edges.

And we are going to prove the following two claims:

• a) in every round, at least one edge  is deleted from $G^f$
• b) an edge is added or deleted from $G^f$ at most $n$ times

Since there are totally $m$ edges, the number of rounds will be no more than $mn$.

For claim a), at least one edge $e$ in $P$ is fully occupied since $b$ is the min residual capacity along $P$. And such $e$ will be deleted afterwards.

For claim b), let’s see what happened when an edge is added to or deleted from $G^f$:

• if $\overrightarrow{vw}\in P$ is a forward edge then
• $\overrightarrow{vw}$ is deleted if it is fully occupied (i.e. $f_{vw} = c_{vw}$)
• $\overrightarrow{wv}$ is added if previously $f_{vw}=0$
• if $\overrightarrow{zv}\in P$ is a backward edge then
• $\overrightarrow{zv}$ is deleted if flow on it is removed (i.e. $f_{vz} = 0$)
• $\overrightarrow{vz}$ is added if previously $f_{vz}=c_{vz}$

In $G^f$, let $level(v)=$ minimum number of edges in paths from $s$ to $v$. Note that $G^f$ is changing so $level(v)$ may also changes.

Claim: $level(v)$ does not decrease during the execution of the algorithm

Proof: Note that in step 3 we take the shortest path $P$.

Let $P=v_0\to v_1\to \dots \to v_l$ where $v_0=s, v_l=t$. We know that $level(v_0)=level(s)=0$.

Consider the relation between $level(v_i)$ and $level(v_{i+1})$:

• $level(v_{i+1}) \leq level(v_i) + 1$ by definition of $level(\cdot)$
• $level(v_{i+1}) \geq level(v_i) + 1$ since otherwise there exist a shorter path $s\to\dots\to v_{i+1}\to\dots\to t$

Thus we know $level(v_{i+1}) = level(v_i)+1$ and $level(v_i)=i$ in $P$.

For any $v\in G, level(v)$ decreases iff some edge $\overrightarrow{uv}$ is added where $level(u) < level(v)-1$ so $s\to\dots\to u \to v$ makes $v$ nearer to $s$. However, in order to add such $\overrightarrow{uv}$ to $G^f$$\overrightarrow{vu}$ must be in the shortest path $P$ first. Thus we know $level(u) = level(v)+1$. $\qquad\blacksquare$

So $level(v)$ must stay the same or increase during the execution of the algorithm.

Now consider what happens if an edge $\overrightarrow{vw}$ is deleted from and later added into $G^f$:

• When it is deleted we know $level(w)=level(v)+1$
• When it is added later we know $level(v)'=level(w)'+1$

Since $level(\cdot)$ never decrease we know $level(v)'=level(w)'+1\geq level(w)+1=level(v)+2$. Which means if an edge $\overrightarrow{vw}$ is deleted and added later then $level(v)$ at least increases by 2.

Thus an edge can be deleted and added later for no more than $n/2$ times since $level(\cdot)\leq n$.

And remember that at least 1 edge is deleted each round we know the total number of rounds is no more than $nm$.

Thus the overall running time of Edmonds-Karp algorithm is $O(nm^2)$.

Best algorithm for max-flow problem in current runs in $O(nm)$ time by [Orlin ’13].