MF: Algorithms

Ford-Fulkerson: PDF of Eric’s handwritten notes are here.
Edmonds-Karp: PDF of Eric’s handwritten notes are here.

Max-flow problem

Sending supply (e.g., internet traffic, products) from vertex $s$ to vertex $t$ without exceeding edge capacities.

Flow network

Directed graph $G=(V,E)$ with designated source $s\in V$ and sink $t\in V$ ; a capacity $c_e>0$ for each $e\in E$ .

$f_e$ is the flow along the edge $e$ . We want to maximize the flow from $s$ to $t$ .

Constraints:

Capacity constraint: for all $e\in E$ , $0\le f_e\le c_e$
Conservation of flow: for all $v\in V\backslash\{s\cup t\}$ , flow-in $v$ = flow-out $v$ , in other words:
$\sum_{\overrightarrow{wv}\in E}f_{wv}=\sum_{\overrightarrow{vz}\in E}f_{vz}$

$\text{size}(f)$ = total flow sent = flow-out $s$ = $\sum_{\overrightarrow{sv}\in E}f_{sv}$ = flow-in $t$ = $\sum_{\overrightarrow{zt}\in E}f_{zt}$ .

Simple algorithm idea

(see handwritten notes for an example)

start with $f_e=0$ for all $e\in E$
find an s-t path $p$ with available capacity
increase the flow along $p$ until some edge hits its capacity
repeat until no such s-t path exists

This approach doesn’t work, since sometimes need to decrease flow along some edges to increase the total flow (see the handwritten notes for such an example).

Residual network

For a flow network on $G=(V,E)$ with capacities $c_e$ and flow $f_e$ , residual network $G^f=(V,E^f)$ has edges:

if $\overrightarrow{vw}\in E$ and $f_{vw}<c_{vw}$ , then add $\overrightarrow{vw}$ to $G^f$ with capacity $c_{vw}-f_{vw}$
if $\overrightarrow{vw}\in E$ and $f_{vw}>0$ , then add $\overrightarrow{wv}$ to $G^f$ with capacity $f_{vw}$

Ford-Fulkerson algorithm

set $f_e=0$ for all $e\in E$
build the residual network $G^f$ for the current for $f$
check for a s-t path $P$ in $G^f$ , if there is no such path, return $f$ as the output
let $c(P)$ be the minimum capacity along $P$ in $G^f$
augment along by :
- for a forward edge $e\in P$ , increases $f_e$ by $c(P)$
- for a backward edge $\overrightarrow{vw}\in P$ , decrease $f_{wv}$ by $c(P)$
repeat from step 2.

Runtime

If capacities are integers, then the flow increases by $\ge 1$ unit each iteration. So if $C$ = size of max-flow, it requires $\le C$ iterations.

Each iteration involves a DFS or BFS, so takes $O(|V|+|E|)=O(|E|)$ time (assuming $G$ is connected). Therefore the overall runtime is $O(|E|C)$ . This is pseudo-polynomial since it depends on the numbers in the input. We want the running time to be independent of the capacities and the size of the flow.

Better algorithm: [Edmonds-Karp ’72] takes the shortest augmenting path in $G^f$ , which results in $O(|V||E|)$ rounds, $O(|V||E|^2)$ total time.

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.

To analyze the running time of the Edmonds-Karp algorithm, 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

Hence, since there are $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 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 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)$ .

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