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^{'}$ :
- $(f ↑ f^{'}) (u, v) = f (u, v) + f^{'} (u, v) - f^{'} (v, u) 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) = m i n {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 (V E)$
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 (E f)$	DFS
$O (V E^{2})$	Edmonds-Karp algorithm
$O (V^{2} E)$ , $O (V^{3})$	Push-relabel algorithms