Ford-Fulkerson Method

Summarized notes on Introduction to Algorithms, Chapter 26

many implementations with varying running times → "method" not "algorithm"
3 core ideas: residual networks, augmenting paths, cuts
iteratively increases the value of the flow
- initially each edge has flow value 0
- on each iteration increase flow value by finding augmenting path in residual network $G_f$
- overall flow increases on each iteration; flows on specific edges may increase or decrease
- augment the flow until residual network has no more augmenting paths
- on termination this process yields a maximum flow

Ford-Fulkerson-method(G, s, t)
    initialize flow f to 0
    while there exists an augmenting path p in the residual network G_f
        augment flow f along p
    return f

Residual networks

$G_f$ consists of edges with capacities that represent how we can change the flow on edges in $G$
Only edges in $G_f$ are those that can admit more flow → edges of $G$ that equal their capacity are not in $G_f$
$G_f$ may contain edges that are not in $G$:
- when flow value needs to decrease place edge $(v, u)$ in $G_f$ with capacity $c_f = f(u, v)$
- residual edges allow sending back flow that has been sent along an edge
residual capacity formal definition:
- $c_f = c(u,v) - f(u,v)$ if $(u,v) \in E$
- $c_f = f(v,u)$ if $(v, u) \in E$
- $c_f = 0$ otherwise
- note: only one can be true since no reverse edges!
residual network if $G_f = (V, E_f)$ where
- $E_f = { (U,v) \in V \times C : c_f(u, v) > 0}$
- only includes residual edges with capacity greater than 0
- edges in $E_f$ are either edges in $E$ or their reversals → $|E_f| \leq 2 |E|$
Residual network has same properties as a flow network BUT does not satisfy the definition because it can have reverse edges
augmentation of flow flow $f$ by $f'$:
- $\displaystyle (f \uparrow f')(u, v) = f(u,v) + f'(u,v) - f'(v,u) \qquad \text{if} (u,v) \in E$
- 0 otherwise
cancellation - pushing flow on the reverse edge in the residual network

Augmenting Paths

augmenting path is a simple path from $s$ to $t$ in residual network $G_f$
flow on edge $(u,v)$ of augmenting path can be increased by up tp $c_f(u,v)$
in image above: grey path is augmenting path
- smallest residual capacity is 4
- we can increase flow through each edge by 4
residual capacity of augmenting path $p$:
$c_f(p) = min\{c_f(u,v):(u, v)$ is on $p\}$
$f_{p}(u,v) = c_f(p)$ if $(u,v)$ is on $p$; 0 otherwise

Cuts of flow networks

cut is a partition of flow network $V$ into $S$ and $T = V-S$ such that $s \in S$ and $t \in T$
net flow across cut:
$$f(S, T) = \sum_{u \in S} \sum_{v \in T} f(u,v) - \sum_{u \in S} \sum_{v \in T} f(v, u) $$
capacity of cut:
$$c(S, T) = \sum_{u \in S} \sum_{v \in T} c(u,v) $$
for capacity only count edges from $S$ to $T$
for flow consider edges from $S$ to $T$ minus reverse edges from $T$ to $S$
minimum cut is a cut whose capacity is minimum over all cuts of the network
for a given flow $f$ the net flow across any cut is the same and equals $|f|$ value of flow → let $(S, T)$ be some cut of $G$, then $f(S, T) = |f|$

Max-flow min-cut theorem

flow is maximum iff residual network contains no augmenting paths
more formally, following conditions are equivalent:
1. $f$ is the maximum flow in $G$
2. The residual network $G_f$ contains no augmenting paths
3. $|F| = c(S, T)$ for some cut $(S, T)$ of $G$

Basic Ford-Fulkerson algorithm

in each iteration: find some augmenting path $p$ and use $p$ to modify flow $f$
each edge in $p$ is an edge in either $G$ or $G_f$
$c_f(p)$ - temporary variable that stores residual capacity
update flow attribute $(u,v).f$ for each edge $(u, v) \in E$
done when no more augmenting paths exist → result is the maximum flow

Pseudo code implementation

Ford-Fulkerson(G, s, t)
    for each edge (u, v) \in G.E
        (u.v).f = 0
    while there exists a path p from s to t in the residual network G_f
        c_f(p) = min{ c_f(u, v) : (u, v) is in p }
        for each edge (u, v) in p
            if (u, v) in E
                (u, v).f = (u, v).f + c_f(p)
            else
                (v, u).f = (v, u).f - c_f(p)

Example

Edmonds-Karp algorithm

use BFS to find augmenting path
- each edge has unit weight
- choose shortest path from $s$ to $t$ in residual network
total number of flow augmentations is $O(VE)$
critical edge of augmenting path: $c_f(p) = c_f(u,v)$
- after augmenting the path this critical edge is no longer in $G_f$
- at least one edge on any augmenting path must be critical
- edge can become critical at most $|V| / 2$ times

Complexity

Running time	algorithm
$O(Ef)$	DFS
$O(VE^2)$	Edmonds-Karp algorithm
$O(V^{2}E)$, $O(V^3)$	Push-relabel algorithms

Running time	algorithm
\(O(Ef)\)	DFS
\(O(VE^2)\)	Edmonds-Karp algorithm
\(O(V^{2}E)\), \(O(V^3)\)	Push-relabel algorithms