Network Flow

A flow network comprises of :

- A directed graph $G(V,E)$

- Non-negative capacities on each edge $c(u,v)$

- A source $s$

- A sink $t$

Definition: Flow

Flow is a function $f:E\rightarrow \mathbb{R}$ such that the following properties hold

- Bounded by Capacity: $f(u,v) < c(u,v)$

- Anti-Symmetry: f(u,v) = -f(v,u)

- Conservation of flow: For any node $u$ that is neither source nor sink, $\sum_{v\in V} f(u,v) = 0$

- Special vertices $s$ and $t$ such that all flow starts from $s$ and ends at $t$ 

Definition: Value of Flow

$\text{Value of flow} = |f| = \sum_v f(s,v)$

Definition: Residual Capacity

Given the capacity $c$ and flow $f$, the residual capacity of an edge $u \rightarrow v$ is 

\begin{align}
c_f(u,v) = c(u,v) - f(u,v)
\end{align}

Note - Even if there is no directed edge $u \rightarrow v$ in the graph, i.e $c(u,v) = 0$ it might still have a non-zero residual capacity.

Definition: Residual Graph

For a flow $f$ in a graph $G(V,E)$ the residual graph $G_f(V,E_f)$ is the graph with all edges with positive residual capacity, i.e

\[
E_f = \{(u,v)\in \left(V \times V\right)| c_f(u,v)>0\}
\]

Note - Because of the note above $|E_f|<2|E|$ because each edge in $G$ can induce at most 2 edges in $G_f$.

Lemma: 
The flow generated by adding the flows in the graphs $G(V,E)$ and $G_f(V,E_f)$ is also a valid flow in $G$ with a higher flow value
\[

|f+h| = |f| + |h|

\]

Note - $(f+h)(u,v)$ is defined as $f(u,v) + h(u,v)$.

Definition: Augmenting Path
For graph $G$ and a flow $f$, any directed path, $\pi$ from $s$ to $t$ in $G_f$ is called an augmenting path. The maximum flow that can be pushed through $\pi$ is denoted by $c_f(\pi)$ where
\[
c_f(\pi) = \max_{(u\rightarrow v)\in \pi} c_f(u,v)
\]
Note - $c_f(\pi)$ is always positive by definition of Residual Graph.

Lemma: Improving the flow in $f$ using an Augmenting Path
Let $f$ be a flow in $G$ and $f_{\pi}$ be a flow on an augmenting path, $\pi$, in $G_f$. The $f+f_{\pi}$ is a better flow in $G$ since $|f+f_{\pi}| = |f| + |f_{\pi}| > |f|$.

Problem: Max Flow
Given a network flow, find the maximum flow, i.e, maximum possible value of $|f|$.

Algorithm: Ford Fulkerson Method
1. Initialize $f(u,v) = 0 \; \forall \; (u,v) \in E$
2. Compute residual graph $G_f$
3. Find an augmenting path, $\pi$, in $G_f$
4. Update flow in $G$ by $f \leftarrow f + f_{\pi}$
5. Repeat 2-5 until there are no augmenting paths left in $G_f$

Definition: Directed Cut
A directed cut $(S,T)$ in a flow network is a partitioning of $V$ into disjoint sets $S$ and $T = V\setminus S$ such that $s\in S$ and $t\in T$. Standard terminology -
- Net flow of $f$ across a cut $(S,T)$, is $f(S,T) = \sum_{u\in S, v\in T}f(u,v)$
- Capacity of cut $(S,T)$ is $c(S,T) = \sum_{u\in S, v\in T}c(u,v)$
- Minimum cut is the cut with the minimum capacity (*\ important \*)

Lemma: Value of flow in network is the flow across any cut
$f(S,T) = |f| \; \forall \; \text{cuts} \; (S,T)$
(*\Proof is a one liner but worth looking at\*)

Lemma: Flow is bounded above by capacity of any cut $(S,T)$ in G
$|f| \leq c(S,T) \; \forall \; \text{cuts} \; (S,T)$

Theorem: Max-flow Min-cut 
If $f$ is flow in a flow network $G(V,E)$ with source $s$ and sink $t$, then the following statements are equivalent
A. $f$ is the Max-flow
B. $\nexists$ augmenting path in $G_f$
C. $\exists \; \text{cut} \; (S,T) \ni |f| = c(S,T)$ and $(S,T)$ is a Min-cut

Proof:
$(A \implies B)$
If augmenting path $\pi$ did exist in $G_f$ then we could have further improved the flow in $G$ by the amount $|f_{\pi}| = c_f(\pi)$. Hence a contradiction

$(B \implies C)$
Define $S = \{v | v \in V \; and \; \exists \; \text{a path from s to v in} G_f\}$. Let $T = V \setminus S$. Then,
\[
|f| = f(S,T) = \sum_{x\in S, y\in T}f(x,y) = \sum_{x\in S, y\in T}c(x,y) = c(S,T)
\]
Note - If $f(x,y) \neq c(x,y)$, then $c_f(x,y) > 0 \implies (x \rightarrow y)$ is an edge in $G_f$. This would further have implied that $y \in S$ which contradicts the construction of S.

Also, $(S,T)$ has to be a Min-cut because if it were not then it would have implied that $\exists \; cut (S', T') \ni c(S',T') < c(S,T) = |f|$. But we know that $|f| \leq c(S,T) \; \forall (S',T')$. Hence a contradiction.

$(C \implies A)$
Since $|f|$ is bounded above by the capacity of any cut and we have $|f| = c(S,T)$ for some cut, implies that $|f|$ is the max-flow.

Hence proved.

Conclusion
By Max-cut Min-Flow theorem, it follows that if Ford-Fulkerson terminates then it would be a max-flow. But does Ford-Fulkerson terminates?

Claim: Ford-Fulkerson terminates for integral edge capacities
- Ford Fulkerson only performs additions, subtractions and min operations.
- So if it finds an augmenting path, $\pi$, then $c_f(\pi)$ is a positive integer, i.e, $c_f(\pi) \geq 1$.
- In every iteration we would be improving the flow by at least 1.
- If the value of max-flow is $|f^*|$ then in at most $|f^*|$ steps the algorithm will terminal
- In every iteration calculating the augmenting path takes $O(|E|)$ time (BFS or DFS).
- Hence, the algorithm run in $O(|f^*| |E|) $

Integrality Theorem
If all capacities are integral, then the flow $|f|$ generated by Ford-Fulkerson is integral since max-flow equals min-cut which is integral. Also the flow $f(u,v)$ on every edge is integral.

Algorithm: Edmonds - Karp
It is an efficient implementation of Ford-Fulkerson using BFS to find the shortest augmenting path in each iteration. It is meant to deal with the situation where $|f^*|$ is very large.

Definition: 
For a flow $f$, $\delta_f(v)$ is the length of the shortest path from $s$ to $v$ given that each path is of unit length.

Lemma: $\delta_f(v)$ increases monotonically with every flow augmentation

Lemma: Bound on the number of disappearances of an edge in residual graph
The number of times an edge can disappear (and reappear) in the residual graph is at most $|V|/2$.

Proof:
- Let $f$ be the flow in the iteration when edge $(u\rightarrow v)$ disappears from $G_f$
- $(u\rightarrow v)$ must have been in the augmenting path $\pi_f$
- $\delta_f(v) = \delta_f(u) + 1$
- Let $g$ be the flow in the iteration when edge $(u\rightarrow v)$ reappears in in $G_g$
- $(v\rightarrow u)$ must have been in the augmenting path $\pi_g$
- $\delta_g(u) = \delta_g(v) + 1$
- By monotonicity of $\delta$, $\delta_g(u) \geq \delta_f(u) + 2$
- But $\delta_g \leq |V|$
- This can happen at most $|V|/2$ times
Hence proved

Time Complexity of Edmonds - Karp
- In every iteration, at least one edge (namely the one which realizes the residual capacity of the augmenting path in the residual graph) will disappear.
- Total number of disappearances is $\frac{|V||E|}{2}$
- In each iteration finding the shortest path takes $O(|E|)$ time
- Algorithm runs in $O(\frac{|V||E|^2}{2})$ time

Applications of Max-Flow
- Maximum Bipartite Matching can be solved in $O(|V||E|)$ time
- There is a simple extension for multiple sources and sinks by simply connecting them with a Super source and sink with edges of infinite capacity