# Maximum Flow¶

A flow network is a directed graph where each edge is labeled with a capacity (non-negative number) and there are two distinguished vertices: the source $s$ and sink $t$.

A flow is a function $f$ that maps each edge to a number such that

• flow does not exceed the capacity: $$0 \leq f(u,v) \leq c(u,v)$$
• flows into each vertex $v$ equal flows out: $$\sum_u f(u,v) = \sum_w f(v,w)$$

The value of a flow, written $|f|$, is the sum of the flows out of the source minus the flows into the source. $$|f| = \sum_u f(s,u) - \sum_v f(v,s)$$

The maximum flow problem is to find the flow with the maximum value for a given flow network.

## Example Flow¶

In the following graph, we've labeled each edge with two number, written $f:c$, where $f$ is the flow and $c$ is the capacity. The flow value is $4$, the sum of the three out edges of $S$.

## Residual Network¶

The residual network of a flow network $G$ and flow $f$ is another graph $G_f$ with the same vertices as $G$. For each edge $(u,v) \in G$:

• if there is remaining capacity, then there is an edge $(u,v) \in G_f$ whose residual capacity is $c(u,v) - f(u,v)$.
• if the flow is positive, then there is a backward edge $(v,u) \in G_f$ whose residual capacity is $f(u,v)$.

The residual network includes just the edges that can be used to add or remove flow from the network.

We can go in the other direction and compute the residual capacity of an edge in the residual network, $e \in G_f$.

The following is the residual network for the example graph. (Ignoring the backward edges for now.)

Instead of explicitly creating the residual network, we sometimes would just like to navigate it by creating its edges on the fly.

## Augmenting Paths¶

An augmenting path is a path from the source to the sink (without cycles) in the residual network.

The residual capacity of an augmenting path is the smallest of the residual capacities of all the edges on the path.

Lemma 26.2 and Corollary 26.3 Given a flow network $G$ and a flow $f$, you can add the residual capacity of any augmenting path in $G_f$ to all the edges in the path to obtain a new flow $f'$ and $|f'| > |f|$.

We can find an augmenting path by applying Depth-First Search to the residual network. The following is an augmenting path in the example graph with a residual capacity of $1$.

And here's the flow network with the residual capacity added to the flows on the augmenting path.

The Ford-Fulkerson method repeatedly finds augmenting paths and adds their residual capacity to the flow.

It stops when it can no longer find an augmenting path.

But does that coincide with finding the maximum flow?

## Max-flow Min-Cut Theorem¶

This theorem will tell us that a flow is maximum if and only if there are no augmenting paths in the residual network.

But first we have to learn what a min-cut is.

A cut $(S,T)$ of a flow network includes the source on one side $S$ and the sink on the other $T$.

The net flow across a cut $f(S,T)$ is the sum of the flows from $S$ to $T$ minus the flows from $T$ to $S$.

The capacity of a cut $c(S,T)$ is the sum of the capacities of the edges that cross from $S$ to $T$.

The minimum cut of a network is a cut whose capacity is minimum with respect to all other cuts.

Lemma 26.4 The net flow across any cut is equal to the value of the flow.

The following is a cut in the example graph. The net flow across this cut is $4$ which indeed matches the flow value (the sum of the flows leaving $S$). The capacity of this cut is $11$.

Corollary 26.5 The value of every flow is no larger than the capacity of any cut.

Theorem 26.6 (Max-flow min-cut theorem) The following conditions are equivalent:

1. $f$ is a maximum flow
2. $G_f$ contains no augmenting paths
3. $|f| = c(S,T)$ for some cut $(S,T)$. Proof We first show that (1) implies (2). Towards a contradiction, suppose there is an augmenting path. We add its residual capacity to $f$ to get a greater flow, but that contradicts that $f$ is a maximum flow.

Next we show that (2) implies (3). Since there are no augmenting paths, we create a cut $S$ of all the nodes reachable from the source in the residual graph and put the rest in $T$. By Lemma 26.4, we have $$|f| = f(S,T)$$ and by definition, $$f(S,T) = \sum_{u\in S} \sum_{v\in T} f(u,v) - \sum_{v\in T}\sum_{u\in S} f(v,u)$$

• For each edge $(u,v)$ going from $S$ to $T$, we know $f(u,v) = c(u,v)$ because otherwise this edge would be in the residual network and there would be a path from $s$ to $v$ (which there is not).
• For each edge $(v,u)$ going from $T$ to $S$, we know $f(v,u) = 0$ because if it were positive, there would be a backward edge $(u,v)$ in the residual network, and again there would be a path from $s$ to $v$.

Thus, the above equation simplifies to $$f(S,T) = \sum_{u\in S} \sum_{v\in T} c(u,v)$$ which means $$f(S,T) = c(S,T)$$

Finally, we show that (3) implies (1). So there is a cut $(S,T)$ such that $|f| = c(S,T)$. Suppose $f'$ is another flow. By Corollary 26.5, $|f'| \leq c(S,T)$. So $|f'| \leq |f|$.

QED

## Ford-Fulkerson Algorithm for Maximum Flow¶

The algorithm performs the following steps:

1. Initialize the flow on every edge to 0.
2. Compute the residual network G_flow and look for an augmenting path aug_path.
3. If there is no augmenting path, return the current flow.
4. Otherwise, augment the flows on the path with the residual capacity and go to step 2.

## Ford-Fulkerson on the Example Graph¶

The following shows each step of the Ford-Fulkerson algorithm on the example graph. Some augmenting paths involve a "backward" edge in the residual graph, which we depict as a blue edge in the graph. The augmenting path traverses the backward edge in reverse, which removes some flow from that edge and adds it to another edges.

## Time Complexity of Ford-Fulkerson¶

• The while loop iterates at most $|f|$ times, incrementing the flow by at least $1$ each time.
• The intialization loop is $O(m)$ because it iterates over all the edges.
• residual_network is $O(m)$ for the same reason.
• DFS_find_path is $O(n + m)$.
• residual_capacity is $O(m)$ (in the worst case, the path contains all the edges).
• Total: $O(|f|(n + m))$ or $O(|f|m)$ assuming $n < m$.

# Edmonds-Karp Algorithm for Maximum Flow¶

The Edmonds-Karp algorithm is almost the same as Ford-Fulkerson but it instead uses Breadth-First Search to find augmenting paths.

## Time Complexity of Edmonds-Karp¶

The Edmonds-Karp algorithm has time complexity $O(n m^2)$. This is because the number of iterations through the while loop is $O(nm)$ (explained below) and the body of the loop is $O(m)$.

By using BFS we restrict the search for augmenting paths to shortest paths.

Consider the distance from the source to all other vertices in the residual network. That distance either stays the same or increases after each augmentation. The reason is that when we augment the flow, at least one edge $(u,v)$ on a shortest path is removed from the residual graph, causing the distances to vertices further down the path to possibly increase. That edge may get added back later via flow through its "backward" edge, but when it does, it will be via a strictly longer path. Here's why:

• When $(u,v)$ is removed $$\delta_f(s,v) = \delta_f(s,u) + 1$$
• When $(u,v)$ is added back via flow on the backward edge $(v,u)$, we have $$\begin{array}{ll} \delta_{f'}(s,u) &= \delta_{f'}(s,v) + 1\\ &\geq \delta_f(s,v) + 1\\ &= \delta_f(s,u) + 2 \end{array}$$

Now, a path can only get so long, up to the number of vertices. So the maximum number of times we can augment the flow is the number of edges times the number of vertices: $O(nm)$.

# Goldberg's Push-Relabel Algorithm¶

The push-relabel approach to computing maximum flow is more efficient than Edmonds-Karp, with an $O(n^3)$ time complexity. It is based on the following ideas:

• Attach a resevoir to each node to hold excess flow.
• Push the excess flow in a node to its neighbors in the residual network.
• Associate a height with each node and only push flow down-hill to nodes of one-less height.
• If a node has excess flow but no down-hill neighbors, then increase its height via the relabel operation.

At the beginning, the source is placed at height $n$ and all other vertices at height $0$. The neighbors of the source are given excess flow equal to the capacity of the edge from the source. The source is given a negative excess equal to the capacities of its out-edges.

## Push¶

The push operation can be applied along an edge when the source node has positive excess flow, the residual capacity of the edge is positive, and the height of the source is one greater than the target.

The push operation moves as much of the excess flow as it can (up to the residual capacity of the edge) from the source to the target of the edge. It also updates the flow for the edge. We'll explain the update_overflow function later.

A saturating push is a push that increases the flow on the edge to be equal to the capacity. A saturating push causes the edge to be removed from the residual network.

## Relabel¶

The relabel operation is applicable to a node when it contains excess flow and all of its neighbors in the residual network are at equal or greater height.

The relabel operation increase the height of the node to one greater than the lowest of its neighbors.

We'll use the following function to display the excess flow and height of each node.

## Push and Relabel Examples¶

Consider again the following example network that has been initialized as described above.

Node A has excess flow but no downhill neighbors, so we raise it to height 1.

Now we can push the excess from node A to node C.

Similarly, we can relabel C and then push 2 units of its excess to T.

## Implementation of Goldberg's Push-Relabel Algorithm¶

By repeatedly pushing and relabeling, the maximum flow will eventually reach the sink T.

However, there is often some excess flow remaining in some of the vertices. That means the flow does not yet satisfy the "flows-in equals flows-out" constraint.

So the process of pushing and relabeling continues, raising many of the vertices above the source vertex and returning all the excess flow to the source.

For efficiency, we'd like to quickly identify nodes that can be relabeled or from which we can push some flow. Those are nodes that are overflowing, i.e., that have positive excess flow. So we maintain a list of nodes named overflow. The update_overflow function adds or removes the given node from the overflow.

The algorithm proceeds as follows:

• Initialize the height of the source to $n$ and all other nodes to $0$.
• Initialize the flow for the out-edges of the source to their capacity. All other edges get a flow of $0$.
• Initialize the excess for each neighbor of the source to the capacity of the in-edge from the source. The excess for the source is the negative of the sum of the excess of its neighbors. Initialize the excess to $0$ for all other nodes.
• Add nodes with positive excess to the overflow list.
• While there are nodes in the overflow list, repeat the following steps
1. Consider the first node in the list. If it is the sink, discard it.
2. If it can be relabeled, do so and go back to step 1.
3. Otherwise we push from this node along one of its out-edges, which possibly adds or removes nodes from the overflow list.

## Time Complexity of Goldberg's Push-Relabel Algorithm¶

Let $n$ be the number of vertices in the graph and $m$ the number of edges.

• The initialization is $O(n)$.
• The maximum height of any node is $2n-1$, so the number of relabel operation is in $O(n^2)$.
• The number of saturating pushes is in $O(nm)$.
• The number of non-saturating pushes in in $O(n^2(n + m))$.

So the total time is dominated by the number of non-saturating pushes. Assuming $n < m$, the time complexity is $O(n^2 m)$.