Reaves.dev

v0.1.0

built using

Phoenix v1.7.20

@rapscallionreaves Gitlab Posts Notes Talks Showcase About

Max Flow Min Cut

Stephen M. Reaves

::

 2025-02-25

Proving that the maximum flow is equal to the minimum st-cut

Summary

We prove that we can partition the graph by creating a cut that divides s and t, and the minimum such cut is the same size of the maximum flow from the Ford-Fulkerson. To construct such a partition, we simply include everything reachable from s in L, and everything else in R, using the residual graph from Ford-Fulkerson.

Contents

Recap of Ford-Fulkerson Algorithm

Input: flow network

  • directed graph G=(V,E) with s,t in V and capacities > 0

Output: flow f∗ f^* of max size

  • size(f)=fout(s)=fin(t) \text{size}(f) = f^{out}(s) = f^{in}(t)

When did Ford-Fulkerson stop?

  • When there was no augmenting path in residual Gf∗ G^{f^*}

Lemma: For a flow f∗ f^* , if no augmenting path in Gf∗ G^{f^} , then f∗ f^ is a max-flow

It takes O(n+m) time to check if f∗ f^* is a max-flow. We simply run BFS on it.

Min-Cut Problem

A cut is a partition of V=L⋃R V = L \bigcup R

An st-cut is a cut where s∈L,t∈R s \in L, t \in R

capacity(L,R)=∑vw→∈E:v∈L,w∈Rcvw \text{capacity}(L,R) = \displaystyle\sum_{\overrightarrow{vw} \in E: v \in L, w \in R} c_{vw} = capacity from L to R

Input: Flow network

Output: st-cut with minimum capacity

Max-Flow Min-st-cut

Size of max-flow = min capacity of st-cut
Theorem

Proof: max-flow ≤ \le min st-cut & max-flow ≥ \ge min st-cut

for any flow f and st-cut(L,R), size(f) ≤ \le capacity(L,R)

The intution is that the flow is going from s to t, so at some point it needs to go from L to R

size(f)=fout(L)−fin(L) size(f) = f^{out}(L) - f^{in}(L)

fout(L)−fin(L)=−∑vw→∈E:v∈L,w∈Rfvw f^{out}(L) - f^{in}(L) = \phantom{-} \displaystyle\sum_{\overrightarrow{vw} \in E : v \in L, w \in R} f_{vw}

fout(L)−fin(L)=−∑wv→∈E:v∈L,w∈Rfwv \phantom{f^{out}(L) - f^{in}(L) =} - \displaystyle\sum_{\overrightarrow{wv} \in E : v \in L, w \in R} f_{wv}

fout(L)−fin(L)=+∑wv→∈E:v∈L,w∈Lfvw \phantom{f^{out}(L) - f^{in}(L) =}+ \displaystyle\sum_{\overrightarrow{wv} \in E : v \in L, w \in L} f_{vw}

fout(L)−fin(L)=−∑wv→∈E:v∈L,w∈Lfwv \phantom{f^{out}(L) - f^{in}(L) =}- \displaystyle\sum_{\overrightarrow{wv} \in E : v \in L, w \in L} f_{wv}

fout(L)−fin(L)=−v⇝R+v⇝L f^{out}(L) - f^{in}(L) = \phantom{-} v \leadsto R + v \leadsto L

fout(L)−fin(L)=−(R⇝v+L⇝v) \phantom{f^{out}(L) - f^{in}(L) =}- \left( R \leadsto v + L \leadsto v \right)

fout(L)−fin(L)=∑v∈Lfout(v)−∑v∈Lfin(v) f^{out}(L) - f^{in}(L) = \displaystyle\sum_{v \in L}f^{out}(v) - \displaystyle\sum_{v \in L}f^{in}(v)

fout(L)−fin(L)=∑v∈L−s(fout(v)−fin(v))+fout(s) \phantom{f^{out}(L) - f^{in}(L)} = \displaystyle\sum_{v \in L - s}\left(f^{out}(v) - f^{in}(v) \right) + f^{out}(s)

fout(L)−fin(L)=∑v∈L−s(0)+fout(s) \phantom{f^{out}(L) - f^{in}(L)} = \displaystyle\sum_{v \in L - s}\left( 0 \right) + f^{out}(s)

fout(L)−fin(L)=fout(s)=size(f) \phantom{f^{out}(L) - f^{in}(L)} = f^{out}(s) = \text{size}(f)

size(f)=fout(L)−fin(L)≤fout(L)≤cap(L,R) \text{size}(f) = f^{out}(L) - f^{in}(L) \le f^{out}(L) \le \text{cap}(L,R)

Reverse Inequality

max⁡f size(f)≥min⁡(L,R) cap(L,R) \displaystyle\max_f \text{ size}(f) \ge \displaystyle\min_{(L,R)}\text{ cap}(L,R)

Take flow f∗ f^* from Ford-Fulkerson (which has no st-path in residual Gf∗ G^{f^*} )

Let L = vertices reachable from s in Gf∗ G^{f^*}

Let R = V - L

For vw→∈E,v∈L,w∈R,fvw∗=cvw \text{For } \overrightarrow{vw} \in E, v \in L, w \in R, f_{vw}^* = c_vw

For vw→∈E,v∈L,w∈R,f∗out= cap(L,R) \phantom{\text{For } \overrightarrow{vw} \in E, v \in L, w \in R,} f^{*out} = \text{ cap}(L,R)

For zy→∈E,z∈R,y∈L,fzy∗=0 \text{For } \overrightarrow{zy} \in E, z \in R, y \in L, f_{zy}^* = 0

For zy→∈E,z∈R,y∈L,f∗in=0 \phantom{\text{For } \overrightarrow{zy} \in E, z \in R, y \in L,} f^{*in} = 0

size(f∗)= cap(L,R) \text{size}(f^*) = \text{ cap}(L,R)