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

$$\text{cap}(S,T)=\text{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)

$$\text{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

$$\text{val}(f)=\text{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 $\text{cap}(S,T)=\text{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)$

Ford-Fulkerson Algorithm

Assume all capacities are integers.

Start with the zero flow $f=0$. As long as there is a directed $s$-$t$ path $P$ in the residual network $N_f$, augment the flow along $P$.

Let

$$\Delta :=\underset{e\in P}{\min }{c}_f(e)$$

be the minimum residual capacity on the path. Then update the flow by

• increasing $f(e)$ by $\Delta$ on forward edges of $P$
• decreasing $f(e)$ by $\Delta$ on backward edges of $P$

After the augmentation, the value of the flow increases by $\Delta$:

$$\text{val}(f^{\prime })=\text{val}(f)+\Delta$$

Since all capacities are integers, all residual capacities are integers as well, so $\Delta \ge 1$ whenever an augmenting path exists. Therefore every augmentation increases the flow value by at least $1$.

Because the value of any flow is bounded above by the capacity of any $s$-$t$ cut, the algorithm can perform only finitely many augmentations. When no augmenting path exists anymore, the flow is maximum by the characterization above.

Integer capacities

If all capacities are integers, Ford-Fulkerson terminates and returns a maximum flow. Moreover, the final flow is integral on every edge. Its running time is $O(|A|\cdot \mathrm{val}(f^{\ast }))$, since there are at most $\mathrm{val}(f^{\ast })$ augmentations and each search for an augmenting path takes $O(|A|)$ time.