# Max-flow Part I

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:

1. for all $e\in E$, $0\le f_e\le c_e$ (capability constraint)
2. for all $v\in V\backslash\{s\cup t\}$, flow-in $v$ = flow-out $v$: $\sum_{\overrightarrow{wv}\in E}f_{wv}=\sum_{\overrightarrow{vz}\in E}f_{vz}$ (flow is conserved)

$\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

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}, 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

1. set $f_e=0$ for all $e\in E$
2. build the residual network $G^f$ for the current for $f$
3. check for a s-t path $P$ in $G^f$, if there is no such path, return $f$ as the output
4. let $c(P)$ be the minimum capacity along $P$ in $G^f$
5. augment $f$ along $P$ by $c(p)$:
• 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)$
6. repeat from 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). So the runtime is $O(|E|C)$. This is pseudo-polynomial since it depends on the numbers in the input.

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.

For a graph $G=(V,E)$, a cut is a partition $V=S\cup\overline{S}$. For a directed $G=(V,E)$ with two vertices $s,t\in V$, s-t cut is a partition $V=L\cup R$ where $s\in L, t\in R, L\cap R=\emptyset$.

The capacity of a s-t cut is $\text{capacity}(L,R)=\sum_{\overrightarrow{vw}\in E: v\in L, w\in R}c_{vw}=\text{total capacity from }L\rightarrow R$.

Fact: for every flow $f$ and every s-t cut $(L,R)$, $\text{size}(f)\le\text{capacity}(L,R)$.

Max-flow min-cut theorem

$\max_{\text{flow} f} \text{size}(f)=\min_{(L,R)}\text{capacity}(L,R)$.

We”ll show this theorem by proving that for a flow $f$, if there is no augmenting path in the residual network, then there is a s-t cut $(L,R)$ where $\text{size}(f)=\text{capacity}(L,R)$. Hence $\max_{\text{flow} f} \text{size}(f)\ge\min_{(L,R)}\text{capacity}(L,R)$. This also shows that Ford-Fulkerson finds a max-flow.

Advertisements