# Maximum Flow Problem - Concepts - Augmenting paths - Cut - _Residual networks_, $G_f = (V, E_f)$, with _residual capacity_ to reflect how the flow can be increased or decreased. $ c_f(u, v) = \begin{cases} c(u, v) - f(u, v), & (u, v) \in E, \\ f(v, u), & (v, u) \in E, \\ 0, & \text{otherwise} \end{cases} $ $ E_f = \{(u, v) \in V \times V : c_f(u, v) > 0 \} $ - $f\uparrow f' : V \times V \to \mathbb R$, the _augmentation_ of flow $f$ by $f'$ (flow in the residual network) $ (f\uparrow f')(u, v) = \begin{cases} f(u, v) + f'(u, v) - f'(v, u), & (u, v) \in E, \\ 0, & \text{otherwise} \end{cases} $ - This yields a flow with greater _value_: $|f\uparrow f'| = |f| + |f'|$ - _augmenting path_ in residual network $ f_p(u, v) : V \times V \to \mathbb R = \begin{cases} c_f(p), & (u, v) \in p \\ 0 \end{cases} $ - Ford-Fulkerson method - Initialize flow $f = 0$ - While there exists an augmenting path $p$ in residual network $G_f$ - Augment flow $f$ along $p$ - $O(E)$ at each iteration $ 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) $ $ c(S, T) = \sum_{u\in S}\sum_{v\in T} c(u, v) $ - Max-flow min-cut theorem: $|f| = c(S, T)$ is max flow, where $G_f$ contains no augmenting paths - How to find the augmenting path? - with [[bfs|BFS]] and choose one with fewest edges: _Edmonds-Karp algorithm_. Total runtime is $O(VE^2)$.