MaxFlow Problem

Problem

Given a network $N=(V,A,c,s,t)$, find the flow $f$ with the greatest value

Definition - cut

A cut in the network is a partition of the vertex set $V$ into two disjoint subsets $S$ and $T$ such that $s\in S,t\in T$

The capacity of a cut $(S,T)$ is the total capacity of all edges from $S$ to $T$:

$$c(S,T)=\sum _{\begin{array}{c}u\in S\\ v\in T\end{array}}c(u,v).$$

Example

Observation Any s-t cut in a flow network places an upper bound on the value of any feasible flow.

Maximum flow

If we find, for a flow $f$, an $s$-$t$ cut $(S,T)$ such that

$$\mathrm{cap}(S,T)=\mathrm{val}(f)$$

then $f$ is a maximum flow

Lemma

We claim:

$\text{val}(f)\stackrel{(i)}{=}f(S,T)-f(T,S)\stackrel{(ii)}{\le }f(S,T)\stackrel{(iii)}{\le }\text{cap}(S,T)$

(i)

$$\mathrm{val}(f)=\sum _{u\in V:(s,u)\in A}f(s,u)-\sum _{u\in V:(u,s)\in A}f(u,s)$$ $$=\sum _{v\in S}\underset{=0\text{ for }v\ne s}{\underbrace{\left(\sum _{u\in V:(v,u)\in A}f(v,u)-\sum _{u\in V:(u,v)\in A}f(u,v)\right)}}$$ $$=\sum _{(u,w)\in (S\times T)\cap A}f(u,w)-\sum _{(u,w)\in (T\times S)\cap A}f(u,w)$$

($S\times T\cap A$ makes sure those edges exist (equivalently all edges ($u$,$v$) such that $u\in S$ and $v\in V$))

$$=f(S,T)-f(T,S)$$

(ii) proved by showing $f(S,T)\ge 0$ (iii) proved by capacity constraint

Maxflow-Mincut Theorem

Maxflow-Mincut Theorem

In any flow network, the maximum value of a flow equals the minimum capacity of an s-t cut

formally

$${\text{max}}_f\text{val(f)}={\text{min}}_{(S,T)}\text{cap}(S,T)$$

This means we could find a minimum $s$-$t$ cut in finite steps, and a minimal cut always exists.

Characterization of Maximum Flow

Let $N$ be a network (without oppositely directed edges).

A flow $f$ is a maximum flow $⟺$ there is no directed $s$–$t$ path in the residual network $N_f$.

For every maximum flow $f$, there exists an $s$–$t$ cut $(S,T)$ such that

$$\mathrm{val}(f)=\mathrm{cap}(S,T).$$

Proof $⟸$ There is no directed $s$–$t$ path in the residual network $N_f$ $⟹$ there exists an $s$–$t$ cut $(S,T)$ such that $\mathrm{cap}(S,T)=\mathrm{val}(f)$ $⟹f$ is a maximum flow.

$S:=$ nodes in $N_f$ that can be reached from $s$ $T:=V\setminus S$

For all $e\in (S\times T)\cap A$ there is $f(e)=c(e)⟹f(S,T)=\text{cap}(S,T)$ For all $e^{\prime }\in (T\times S)\cap A$ there is $f(e^{\prime })=0⟹f(T,S)=0$ $⟹\text{val}(f)=f(S,T)-f(T,S)=\text{cap}(S,T)$