MF: Max-Flow/Min-Cut

PDF of Eric’s written notes are here.

In this lecture we’ll present the max-flow min-cut theorem and show an application of this theorem to the image segmentation problem.

Flow network

A flow network is defined by a directed graph G=(V,E) with designated source s\in V and sink t\in V, along with 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).