# Mar 6. Maximum flow and minimum cut II

Let $G = (V, E)$ be a directed graph and each edge $(i, j)$ has a capacity $c_{ij} \ge 0$. There are two special vertices $s, t$ referred to as the source and the sink respectively. A flow is a vector in $\mathbb{R}^E$ such that $0 \le f_{ij} \le c_{ij}$ for every edge $(i, j)$. Recall that the value of the flow $val(f) = f(s, V) - f(V, s) = f(V, t) - f(t, V)$.

Recall that the maximum $s, t$ flow is always less than or equal to the capacity of the minimum $s,t$ cut. Let $(S, \bar{S})$ be a $s,t$ cut in the graph such that $s \in S$. Then we have:

$f(S, V) - f(V, S) = \sum_{i \in S} (f(i,V) - f(V, i)) = f(s, V) - f(V, s) = val(f) = f(S, \bar{S}) + f(S, S) - f(S, S) - f(\bar{S}, S) = f(S, \bar{S}) - f(\bar{S}, S) \le f(S, \bar{S}) \le \sum{i\in S, j \in \bar{S}} c_{ij} = c(S, \bar{S})$.

Theorem: For every graph $G$ and capacity $c_{ij} \ge 0$, the value of the maximum $s, t$ flow is equal to the capacity of the minimum $s,t$ cut.

Proof: We need the following definition.

Augmenting Path: An $s$ to $t$ path $P$ is called an augmenting path if for every forward edge $(i, j) \in P$ we must have $f_{ij} < c_{ij}$ while for every backward edge $(i, j) \in P$ we must have $f_{ij}>0$. The idea is that we can route more flow from $s$ to $t$ via $P$ by increasing the flow on the forward edges and decreasing the flow on the backward edges. Note that the amount of flow we can send is the minimum of $c_{ij} - f_{ij}$ for every forward edge $(i, j) \in P$ and $f_{ij}$ for every backward edge $(i, j) \in P$.

Note that if $f$ is a maximum $s, t$ flow then clearly there cannot be any $f$ augmenting paths in $G$. Let us define the set $S = \{ u \mid \exists s, u\text{ augmenting path}\}$. Note that for every forward edge $(i, j)$ coming out of $S$ we must have $f_{ij} = c_{ij}$ while for every backward edge $(i, j)$ coming into $S$ we must have $f_{ij} = 0$. Thus $val(f) = \sum_{i \in S, j \in \bar{S}} f_{ij} - \sum_{i \in S, j \in \bar{S}} f_{ji} = \sum_{i \in S, j \in \bar{S}} c_{ij} - 0 = cap(S, \bar{S})$.

Residual Graph:  For every edge $(i, j)$ such that the flow $f_{ji} = 0$ we set the capacity $c'_{ij} = c_{ij} - f_{ij}$ while the capacity of $c'_{ji} = f_{ij}$. Define the residual graph $G'$ to be the graph on the same set of vertices as $G$ and consisting of edges $(i, j)$ such that $c'_{ij} > 0$. Note that by definition any $s, t$ augmenting path in $G$ is a directed path in the residual graph $G'$. Thus finding an augmenting path reduces to finding a directed $s, t$ path in $G'$.

Choice of augmenting path

• One could choose the maximum (residual) capacity augmenting path from $s, t$. The capacity of a path is defined as the minimum of the residual capacity of the edges in the path.
• Alternatively we could also pick the shortest (number of edges) $s, t$ path in $G'$.

Claim:  Given a flow $f$ and optimal flow $f^*$ in $G$ then there exists a path in the residual graph of $G$ and $f$ such that its capacity is at least $\frac{f^*-f}{m}$.

Proof: Observe that in every $m$ step the difference $f^* - f$ becomes at least $1/2$ of the initial value. Suppose the original capacities are integral then we can only halve till $\log{f^*} \le \log{nC}$ where $C$ is the largest capacity edge in $G$. Thus the running time is $m\log{nC}$. Note that this is polynomial in the size of the input since we need only $\log{nC}$ bits to write down the capacities of all the edges. There is a strongly polynomial algorithm that depends only on $m$ and not on the capacity.