**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)$.

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.

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|$.

**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