# Max-flow Part II

PDF of Eric’s written notes are here.

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}$.

Max-flow problem: given a flow network, find a flow $f$ with $\max\text{size}(f)$. This is closely related to the following min-cut problem.

A cut is a partition of the vertices into two sets $L$ and $R$ such that $V=L\cup R$ and $L\cap R=\emptyset$. This is an s-t cut if $s\in L$ and $t\in R$. For an s-t cut, its capacity is defined as $\text{capacity}(L,R)=\sum_{\overrightarrow{vw}\in E:v\in L, w\in R}c_{vw}=\text{capacity from }L\rightarrow R$.

Min st-cut problem: given a flow network, find an s-t cut with minimum capacity.

Max-flow min-cut theorem: size of max-flow = min capacity of an s-t cut.

We prove the theorem in two directions. The easy direction is that size of max-flow $\le$ min capacity of an s-t cut. We’ll show that for any flow $f$ and any s-t cut $(L,R)$, $\text{size}(f)\le\text{capacity}(L,R)\ (\ast)$. Hence $\max_f\text{size}(f)\le\min_{(L,R)}\text{capacity}(L,R)$.

For an s-t cut $(L,R)$, define $f^{in}(L)=\sum_{\overrightarrow{uv}\in E: u\not\in L,v\in L}f_{uv}=\text{flow into }L$$f^{out}(L)=\sum_{\overrightarrow{vw}\in E: v\in L,w\not\in L}f_{vw}=\text{flow out of }L$.

We show that $\text{size}(f)=f^{out}(L)-f^{in}(L):$ \begin{aligned} f^{out}(L)-f^{in}(L) &=\sum_{\overrightarrow{vw}\in E: v\in L,w\not\in L}f_{vw}-\sum_{\overrightarrow{uv}\in E: u\not\in L,v\in L}f_{uv}\\ &=\sum_{\overrightarrow{vw}\in E: v\in L,w\not\in L}f_{vw}-\sum_{\overrightarrow{uv}\in E: u\not\in L,v\in L}f_{uv}+\sum_{\overrightarrow{vw}\in E: v\in L,w\in L}f_{vw}-\sum_{\overrightarrow{uv}\in E: u\in L,v\in L}f_{uv}\\ &=f^{out}(s)+\sum_{v\in L\backslash\{s\}}\Big(f^{out}(v)-f^{in}(v)\Big)\\ &=\text{size}(f) \end{aligned}

Therefore, for any flow $f$ and any s-t cut $(L,R)$, $\text{size}(f)=f^{out}(L)-f^{in}(L)\le f^{out}(L)\le \text{capacity}(L,R)$, which proves $(\ast)$.

Then we show that $\max_f\text{size}(f)\ge\min_{(L,R)}\text{capacity}(L,R)$. Take the flow $f^*$ produced by the Ford-Fulkerson algorithm. $f^*$ has no augmenting path, which means that there is no s-t path in the residual network $G^{f^*}$. We’ll construct an s-t cut $(L,R)$ where $\text{size}(f^*)=\text{capacity}(L,R)\ (\ast\ast)$. Hence $\max_f\text{size}(f)\ge\min_{(L,R)}\text{capacity}(L,R)$.

Proof of $(\ast\ast):$ for flow $f^*$, let $L$ be those vertices reachable from $s$ in $G^{f^*}$. We know that $t\not\in L$ since there is no s-t path in $G^{f^*}$. Let $R=V\backslash L$ and $(L,R)$ is a s-t cut.

Consider an edge from $L$ to $R$: for $\overrightarrow{vw}\in E$ where $v\in L$ and $w\in R$, we must have $f_{vw}^*=c_{vw}$, otherwise $\overrightarrow{vw}$ in $G^{f^*}$ and $w$ is reachable from $s$, contradiction.

Consider an edge from $R$ to $L$: for $\overrightarrow{zy}\in E$ where $z\in R$ and $y\in L$, we must have $f_{zy}^*=0$, otherwise $\overrightarrow{yz}\in G^{f^*}$ and $z$ is reachable from $s$, contradiction.

Thus, $f^{*out}(L)=\text{capacity}(L,R)$ and $f^{*in}(L)=0$. Therefore, $\text{size}(f^*)=f^{*out}(L)-f^{*in}(L)=\text{capacity}(L,R)$, which proves $(\ast\ast)$.

We also know that any flow $f^*$ with no augmenting paths is a max-flow, since $\text{size}(f^*)=\min \text{s-t cut capacity}$.

Image segmentation

Given an image, separate it into objects. A simpler problem: separate it into foreground and background. Image is on an undirected graph $G=(V,E)$ with $V=\text{pixels}$ and $E=\text{neighboring pixels}$.

For $i\in V$, given likelihood $a_i$ that $i$ is in the foreground and $b_i$ that $i$ is in the background with $a_i,b_i\ge 0$. For $(i,j)\in E$, given separation penalty $p_{ij}\ge 0$.

For a partition $(A,B)$ where $V=A\cup B$ (A = foreground, B = background), define its weight as $w(A,B)=\sum_{i\in A}a_i+\sum_{j\in B}b_j-\sum_{(i,j)\in E: i\in A, j\in B\text{ or }i\in B, j\in A}p_{ij}$.

Goal: find partition $(A,B)$ with maximum weight $w(A,B)$. We can reduce it to min s-t cut problem.

First, we convert it from a maximization to a minimization problem. Let $Q=\sum_{i\in V}(a_i+b_i)$ (note that $\sum_{i\in A}a_i+\sum_{j\in B}b_j=Q-\sum_{i\in A}(b_i)-\sum_{j\in B}(a_j)$). Thus, $w(A,B)=Q-\sum_{i\in A}(b_i)-\sum_{j\in B}(a_j)-\sum_{(i,j)\in E: i\in A, j\in B\text{ or }i\in B, j\in A}p_{ij}$.

Let $w'(A,B)=\sum_{i\in A}(b_i)+\sum_{j\in B}(a_j)+\sum_{(i,j)\in E: i\in A, j\in B\text{ or }i\in B, j\in A}p_{ij}$. $(A,B)$ that maximizes $w(A,B)$ is the same as $(A,B)$ which minimizes $w'(A,B): w(A,B)=Q-w'(A,B)$.

To reduce to max-flow: for an edge $(i,j)\in E$: add edges $i\rightarrow j$ with capacity $p_{ij}$ and $j\rightarrow i$ with capacity $p_{ij}$; add source $s$, for every $i\in V,$ add edges $s\rightarrow i$ with capacity $a_i$; add sink $t$, for every $j\in V$, add edge $j\rightarrow t$ with capacity $b_j$.

In this flow network, for an s-t cut $(A,B)$, we ask what edges cross $A\rightarrow B$? For $j\in B$, get an edge $s\rightarrow j$ of capacity $a_j$, for $i\in A$ get an edge $i\rightarrow t$ of capacity $b_i$, for $(i,j)$ where $i\in A, j\in B$, get an edge $i\rightarrow j$ of capacity $p_{ij}$, and if $i\in B, j\in A$, get an edge $j\rightarrow i$ also of capacity $p_{ij}$.

Therefore, $\text{capacity}(A,B)=w'(A,B)$. So we run max-flow algorithm, the size of the max-flow =$\min_{(A,B)}w'(A,B)$. Thus $\max_{(A,B)}w(A,B)=Q-\min_{(A,B)}w'(A,B)$.