max-flow

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{array}{ll}c(u,v)-f(u,v),& (u,v)\in E,\\ f(v,u),& (v,u)\in E,\\ 0,& \text{otherwise}\end{array}$$ $$E_f=\{(u,v)\in V\times V:c_f(u,v)>0\}$$

• $f\uparrow f^{\prime }:V\times V\to \mathbb{R}$, the augmentation of flow $f$ by $f^{\prime }$ (flow in the residual network)

$$(f\uparrow f^{\prime })(u,v)=\{\begin{array}{ll}f(u,v)+f^{\prime }(u,v)-f^{\prime }(v,u),& (u,v)\in E,\\ 0,& \text{otherwise}\end{array}$$

• This yields a flow with greater value: $|f\uparrow f^{\prime }|=|f|+|f^{\prime }|$
• augmenting path in residual network

$$f_p(u,v):V\times V\to \mathbb{R}=\{\begin{array}{ll}{c}_f(p),& (u,v)\in p\\ 0& \end{array}$$

• 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 and choose one with fewest edges: Edmonds-Karp algorithm. Total runtime is $O(V{E}^2)$.