Notes - ADS HT24, Flow networks

\[(G, s, t, c)\]

Where:

• $G = (V, E)$ is a directed graph
• $s \in V$ is a “source node”
• $t \in V$ is a “sink node”
• $c : E \to \mathbb Z _ {\ge 0}$ is a capacity function

Add another node $v’$ such that $(u,v’)$ and $(v’, v)$ have the capacity from $(u, v)$ and keep $(v, u)$ the same.

Add two more nodes, a “supersource” and “supersink” which connect to each source/sink with infinite capacity.

A partition of $V$ into two sets $A$, $B$ such that $s \in A$ and $t \in B$.

\[\text{cap}(A, B) = \sum_{e \text{ out of } A} c(e)\]

The min-cut problem is the problem of identifying $A$ and $B$ such that the capacity is minimised.

A flow is a function $f : E \to \mathbb R _ {\ge 0}$ that satisfies:

• Capacity constraints: For each edge $e \in E$, $0 \le f(e) \le c(e)$.
• Flow conservation: $\sum _ {e \text{ into } v} f(e)$ = $\sum _ {e \text{ out of } v} f(e)$.

The value of $f$, denoted $ \vert f \vert $ is

\[|f| = \sum_{e \text{ out of } s} f(e)\]

and the maximum-flow problem is then to find a flow with maximum value.

For any flow $f$ and any $s$-$t$ cut $(A, B)$, we have

\[|f| \le \text{cap}(A, B)\]

\[\begin{aligned} |f| &= f^\text{out}(s) - f^\text{in}(s) \quad (\star1) \\\\ &= \sum_{v \in A} (f^\text{out}(v) - f^\text{in}(v)) \quad (\star 2) \\\\ &= \sum_{e \text{ out of } A} f(e) - \sum_{e \text{ into } A} f(e) \quad (\star 3) \\\\ &\le \sum_{e \text{ out of } A}f(e) \\\\ &\le \sum_{e \text{ out of } A}c(e) \\\\ &= \text{cap}(A, B) \end{aligned}\]

where (1, 2, 3) are justified since:

1. This is the definition of $ \vert f \vert $, using the notation that $f^\text{in}(e) = \sum _ {e\text{ into }v} f(e)$ and $f^\text{out}(e) = \sum _ {e \text{ out of }v} f(e)$
2. This is justified by the fact that for $v \in A\setminus\{s\}$, we have the flow in must equal the flow out
3. Because edges with both endpoints in $A$ cancel

Alternative proof: Consider the flow network obtained by adding an edge from $t$ to $s$ with capacity $ \vert f \vert $ in the original flow network and setting $f(t, s) = \vert f \vert $. This is another valid flow.

Then, in the modified network, the flow out of $A$ equals the flow coming to $A$, i.e.

\[\sum_{e \text{ out of } A} f(e) = |f| + \sum_{e \text{ into } A} f(e)\]

Then the LHS is less than or equal to $\text{cap}(A, B)$, (since $f(e) \le c(e)$ for all edges), and the RHS is greater than or equal to $ \vert f \vert $. Then

\[\text{cap}(A, B) \ge |f| + \sum_{e \text{ into } A} f(e) \ge |f|\]

as required.

\[\begin{alignat*}{3} |f| &= \sum_{e \text{ out of }s} f(e) \\\\ &= \sum_{e \text{ out of }s} f(e) - \sum_{e \text{ into }s} f(e) \quad &&(\star1)\\\\ &= \sum_{v \in A} \left( \sum_{e \text{ out of }v} f(e) - \sum_{e \text{ into }v} f(e) \right) \quad &&(\star 2) \\\\ &= \sum_{e \text{ out of } A} f(e) - \sum_{e \text{ into } A} f(e) \quad &&(\star 3) \end{alignat*}\]

with the steps justified since:

• $(\star 1)$: This is just subtracting $0$, since the flow into $s$ is $0$.
• $(\star 2)$: This is justified by the fact that for $v \in A\setminus\{s\}$, we have the flow in must equal the flow out.
• $(\star 3)$: This is justified since the flow cancels for edges with both endpoints in $A$.

\[|f| = \text{cap}(A, B)\]

Because of the weak duality between max-flow and min-cut.

This follows from weak duality, since, if $ \vert f^\star \vert $ is the value of max flow, $ \vert f \vert \le \vert f^\star \vert $. But then $ \vert f^\star \vert \le \text{cap}(A, B)$ by weak duality.

$G _ f$ has the same vertices. For each edge in $G$,

• If $f(e) < c(e)$, add a forward edge $e$ with $c _ f(e) = c(e) - f(e)$.
• If $f(e) > 0$, add a backward edge $e’ = \text{rev}(e)$ with $c _ f(e’) = f(e)$

(both these conditions can be met seperately)

The minimum residual capacity $c _ f(e)$ over $e \in P$.

In this network it would be $10$.

\[\text{Augment}(f, P)(e) = f'(e) = \begin{cases} f(e) + b_p &\text{if } e\in P \\\\ f(e) - b_p &\text{if } \text{rev}(e) \in P \\\\ f(e) &\text{otherwise} \end{cases}\]

We need to check the capacity constraints and the flow conservation property.

• Capacity constraints: Need to check $0 \le f’(e) \le c(e)$
  • If $e \in P$, then $f’(e), f(e) + b _ p$ and $b _ p \le c _ f(e) = c(e) - f(e)$
  • If $\text{rev}(e) \in P$, then $f’(e) = f(e) - b _ P$ and $b _ P \le c _ f(\text{rev}(e)) = f(e)$
  • Otherwise $f’(e) = f(e)$
• Flow conservation: Need to check $\sum _ {e \text{ into } v} f’(e) = \sum _ {e \text{ out of } v} f’(e)$
  • If $v$ is not in $P$, then it is immediate
  • If $v$ is in $P$, flow into / out of $v$ increases by $b _ p$.

Then $ \vert f’ \vert = \sum _ {e \text{ out of } s} f’(e)$, and $s$ has exactly one edge $e$ leaving it on $P$, whose flow has increased by $b _ P$. Then $ \vert f’ \vert = \vert f \vert + b _ P$.

FORD-FULKERSON(G, s, t, c):
	Start with an empty flow f
	(i.e. f(e) = 0 for all e \in E)
	G_f = residual graph of G wrt f

	while exists s-t path P in G_f:
		f = Augment(f, P)
		G_f = residual graph of G wrt f

• When the algorithm terminates, there is no path from $s$ to $t$ in $G _ f$.
• Let $A = \text{reach}(s)$, $B = V \setminus A$. Clearly $(A, B)$ form a cut.
• What is the capacity of $(A, B)$?
  • For edge $e = (u, v)$ in $G$ with $u \in A, v \in B$, $f(e) = c(e)$.
  • For edge $e’ = (v, u)$ in $G$ with $v \in B$, $u \in A$, $f(e’) = 0$, since if this were not true, then $v$ would be reachable from $s$ in $G _ f$.
• Hence $ \vert f \vert = \text{cap}(A, B)$.

FORD-FULKERSON(G, s, t, c):
	Start with an empty flow f
	(i.e. f(e) = 0 for all e \in E)
	G_f = residual graph of G wrt f

	while exists s-t path P in G_f:
		f = Augment(f, P)
		G_f = residual graph of G wrt f

• The while loop runs at most $ \vert f^\star \vert $ times, since at each stage the flow increases by at least $1$, and Ford-Fulkerson terminates at max flow
• $ \vert f^\star \vert \le \vert V \vert C$ where $C$ is the maximum capacity over all edges in the network
• Execution of the loop takes time $O( \vert E \vert )$

Hence total time is

\[O(|V|\cdot|E|\cdot C)\]

CAPACITY-SCALING(G, s, t, c):
	Start with an empty flow f
	(i.e. f(e) = 0 for all e \in E)

	T = largest power of 2 <= maximum capacity over all edges in graph

	while T >= 1:
		calculate G_f(T), where G_f(T) is the subgraph of G_f with edge capacities >= T

		while exists s-t path P in G_f(T):
			f = Augment(f, P)
			Update G_f(T)

		T /= 2

	return f

The subgraph of $G _ f(\Delta)$ with edge capacities $\ge \Delta$.

CAPACITY-SCALING(G, s, t, c):
	Start with an empty flow f
	(i.e. f(e) = 0 for all e \in E)

	T = largest power of 2 <= maximum capacity over all edges in graph

	while T >= 1:
		calculate G_f(T), where G_f(T) is the subgraph of G_f with edge capacities >= T

		while exists s-t path P in G_f(T):
			f = Augment(f, P)
			Update G_f(T)

		T /= 2

	return f

Suppose $f$ is the flow of at the end of the previous iteration, when we were considering $2\Delta$.

By the lemma, we have $ \vert f^\star \vert \le \vert f \vert + 2\Delta m$.

Since each augmentation increases $f$ by at least $\Delta$ (by construction, we are only considering paths where the bottleneck capacity is at least $\Delta$), it must be the case that we have had at most $2 \vert E \vert $ iterations in this phase (if we had more, then we’d end up with a flow where $ \vert f \vert \ge \vert f^\star \vert $, which is impossible).

CAPACITY-SCALING(G, s, t, c):
	Start with an empty flow f
	(i.e. f(e) = 0 for all e \in E)

	T = largest power of 2 <= maximum capacity over all edges in graph

	while T >= 1:
		calculate G_f(T), where G_f(T) is the subgraph of G_f with edge capacities >= T

		while exists s-t path P in G_f(T):
			f = Augment(f, P)
			Update G_f(T)

		T /= 2

• Since we are at the end of the scaling phase, there exists no $s$-$t$ path in $G _ f(\Delta)$.
• Let $A = \text{reach}(s)$ and $B = V \setminus A$.

Then

\[\begin{aligned} |f| &= \sum_{e \text{ out of } A} f(e) - \sum_{e \text{ into } A} f(e) &&(\star 1) \\\\ &\ge \sum_{e \text{ out of } A} (c(e) - \Delta)) - \sum_{e \text{ into } A} \Delta &&(\star2, 3) \\\\ &= \sum_{e \text{ out of } A} c(e) - \sum_{e \text{ out of } A} \Delta - \sum_{e \text{ into } A} \Delta \\\\ &\ge \text{cap}(A, B) - \Delta m &&(\star 4) \\\\ &\ge |f^\star| - \Delta m \end{aligned}\]

Where we have the justifications

• $(\star 1)$: This is a lemma which can be derived from considering $ \vert f \vert = f^\text{out}(s) - f^\text{in}(s)$ and then rewriting as a sum over edges in $A$ by using the flow conservation property.
• $(\star 2)$: For edge $e = (u, v)$ in $G$ with $u \in A$, $v \in B$, $c(e) \le f(e) + \Delta$. This is true because in the residual network, the $e$ has capacity $c(e) - f(e)$. This is less than $\Delta$ since otherwise we would have a connection from $A$ to $B$ in the residual network.
• $(\star 3)$: For edge $e = (v, u)$ in $G$ with $v \in B$, $u \in A$, $f(e) \le \Delta$. Again, this is true since otherwise in $G _ f(\Delta)$, $v$ would be reachable from $s$. (Although this edge is reversed, $(v, u)$ is an edge in $G$, but it becomes $(u, v)$ in $G _ f(\Delta)$)
• $(\star 4)$: The definition of $\text{cap}(A, B)$ is $\text{cap}(A, B) = \sum _ {e\text{ out of } A} c(e)$

Alternative proof: Let $(A, B)$ be the $s$-$t$ cut induced by $f$ on $G _ f(\Delta)$. Then the number of edges crossing the cut is $0$ in $G _ f(\Delta)$, and the number of edges crossing the cut in $G _ f$ is $\le m$. Since the capacity of each edge crossing the cut in $G _ f$ is $< \Delta$, we must have $ \vert f^\star \vert \le \cap(A, B) \le \vert f \vert + m\Delta$ (i.e. the size of the best cut must be less than the flow we have going across the cut in $G _ f(\Delta)$, plus all the possible extra flow we could have if we removed the restriction that the edge weights are $< \Delta$).

CAPACITY-SCALING(G, s, t, c):
	Start with an empty flow f
	(i.e. f(e) = 0 for all e \in E)

	T = largest power of 2 <= maximum capacity over all edges in graph

	while T >= 1:
		calculate G_f(T), where G_f(T) is the subgraph of G_f with edge capacities >= T

		while exists s-t path P in G_f(T):
			f = Augment(f, P)
			Update G_f(T)

		T /= 2

• There are $O(1 + \log C)$ iterations in the outer loop
• $O( \vert E \vert )$ iterations for the inner loop, doing $O( \vert E \vert )$ work each time

So we have

\[O(|E|^2(1 + \log C))\]

EDMONDS-KARP(G, s, t, c):
	Start with an empty flow f
	(i.e. f(e) = 0 for all e \in E)
	G_f = residual graph of G wrt f

	while exists s-t path P in G_f:
		P = s-t path with fewest edges
		f = Augment(f, P)
		G_f = residual graph of G wrt f

	return f

\[O(|V| \cdot |E|^2)\]

• Ford-Fulkerson: pick any path to augment flow, running time $O(mnC)$
• Edmonds-Karp: pick the path with least edges to augment flow, $O(m^2 n)$
• Capacity scaling: restrict attention to paths with all edge capacities $\ge 2^k$ each time, $O(m^2 \log C)$.

• 4 nodes: $s, u, v, t$.
• Edges:
  • $(s, u)$ w/ capacity $C$
  • $(s, v)$ w/ capacity $V$
  • $(u, v)$ w/ capacity $1$
  • $(u, t)$ w/ capacity $C$
  • $(v, t)$ w/ capacity $C$

EDMONDS-KARP(G, s, t, c):
	Start with an empty flow f
	(i.e. f(e) = 0 for all e \in E)
	G_f = residual graph of G wrt f

	while exists s-t path P in G_f:
		P = s-t path with fewest edges
		f = Augment(f, P)
		G_f = residual graph of G wrt f

	return f

• Lemma 1: For any vertex $v \in V$, $d _ i(s, v)$ is non-decreasing with $i$, i.e. $d _ 1(s, v) \le d _ 2(s, v) \le \cdots$
• Lemma 2: If $e$ is a bottleneck edge at time $i$, it will not be used in an augmenting path again until $d _ i(s, t)$ increases

Assuming this:

• The distance between $s$ and $t$ can increase at most $n$ times (since the max distance between $s$ and $t$ is $n$, and the distance is nondecreasing, so in the worst case the distance starts off at $1$ and is incremented $\le n$ times).
• While the distance between $s$ and $t$ is some $d$, an edge becomes a bottleneck $\le 1$ times, so there are at most $m$ augmentations for each $d \in \{1, \cdots, n\}$.
• It takes $O(m)$ time each iteration to find the path $P$ using BFS

Thus the total time is

\[O(m^2n)\]

EDMONDS-KARP(G, s, t, c):
	Start with an empty flow f
	(i.e. f(e) = 0 for all e \in E)
	G_f = residual graph of G wrt f

	while exists s-t path P in G_f:
		P = s-t path with fewest edges
		f = Augment(f, P)
		G_f = residual graph of G wrt f

	return f

• Lemma 1: For any vertex $v \in V$, $d _ i(s, v)$ is non-decreasing with $i$, i.e. $d _ 1(s, v) \le d _ 2(s, v) \le \cdots$
• Lemma 2: If $e$ is a bottleneck edge at time $i$, it will not be used in an augmenting path again until $d _ i(s, t)$ increases

Assuming this:

• The distance between $s$ and $t$ can increase at most $n$ times (since the max distance between $s$ and $t$ is $n$, and the distance is nondecreasing, so in the worst case the distance starts off at $1$ and is incremented $\le n$ times).
• While the distance between $s$ and $t$ is some $d$, an edge becomes a bottleneck $\le 1$ times, so there are at most $m$ augmentations for each $d \in \{1, \cdots, n\}$.
• It takes $O(m)$ time each iteration to find the path $P$ using BFS

Thus the total time is

\[O(m^2n)\]

Proof of Lemma 1: Order the vertices in $G _ i$ in “levels” according to the distance from $s$, so that level $1$ vertices are at distance $1$, level $2$ are at distance $2$, etc.

Let $P$ be some augmenting path from $s$ to $t$ in $G _ i$.

Since $P$ is a shortest path in $G _ i$, it goes through levels $0, 1, \cdots, j$ in that order.

Edges of $P$ are reversed in $G _ {i + 1}$, so they join levels $j, j-1, \cdots, 0$ in that order.

Reversed edges cannot be therefore used in $G _ {i+1}$ as shortcuts to move from level $j _ 1$ to level $j _ 2$ with $j _ 1 < j _ 2$. So $d _ i(s, v) \le d _ {i+1} (s, v)$ for each $v \in V$.

Proof of Lemma 2: Suppose $e = (u, v)$ and let $x = d _ i(s, u)$, $y = d _ i(v, t)$. Then $d _ i(s, v) = x+1$ and $d _ i(u, t) = y+1$, and $d _ i(s, t) = x + y + 1$.

Suppose $e$ reappears in $G _ f$ for the first time at time $j + 1 > i$.

At times $i + 1, \cdots, j$, edge $e$ appears backwards in $G _ f$ as an edge $(v, u)$ since $e$ is a bottleneck of an augmenting path in $G _ i$.

Then edge $(u, v)$ is used at time $j$ in a shortest path $P$ from $s$ to $t$.

By claim $1$, $d _ j \ge d _ i(s, v) = x+1$ and $d _ j(u, t) \ge d _ i(u, t) = y+1$.

So $d _ j(s, t) \ge x + y + 3$, so $d _ {j + 1}(s, t) \ge d _ j(s, t)$.

Hence

\[d_j(s, t) \ge x + y + 3 > x + y + 1 = d_i(s, t)\]