15  Correctness and Min Cut

This section proves Ford Fulkerson correct using the concept of the min \(s-t\) cut.

Objectives. After learning this material, you should be able to:

• Define an \(s-t\) cut \((S,T)\) in the graph and find the value of the cut.
• Explain why Ford Fulkerson stops when it find both a max flow and a min cut.
• Use Ford Fulkerson to find a min \(s-t\) cut in the graph.

15.1 Min cut

To prove that Ford Fulkerson is correct, we’ll need a non-obvious, very mathematically nice strategy. The idea is that the maximum flow is limited by bottlenecks in the graph, where no more flow can squeeze through. If there is a bottleneck where the total capacity to squeeze through is 10, then the max the flow could possibly be is 10. The tricky part is that a bottleneck could contain multiple edges.

A \(s-t\) cut in a directed graph \(G = (V,E)\) is a partition of the vertices into two sets, \(S\) and \(T\), such that \(s \in S\) and \(t \in T\).

Given a capacity function \(c\), the capacity of an \(s-t\) cut \((S,T)\) is the total capacity of edges that cross from \(S\) to \(T\), which is

\[ K(S,T) = \sum_{u \in S, v \in T} c(u,v) . \]

Here, we only sum over pairs \((u,v) \in E\) such that \(u \in S, v \in T\). Meanwhile, given a flow \(f\), the flow across an \(s-t\) cut \((S,T)\) is the total net flow from \(S\) to \(T\), which is

\[ F(S,T) = \sum_{u \in S, v \in T} (f(u,v) - f(v,u)) . \]

The Min \(s-t\) Cut problem is, given an input graph to max flow, to find the \(s-t\) cut that minimizes \(K(S,T)\). This will turn out to be highly related to the max flow problem.

Exercise 15.1 Consider the following input graph and flow. Let \(S = \{s,w,x\}\) and \(T = \{v,t\}\). What is \(K(S,T)\)? What is \(F(S,T)\)? And what is the minimum \(s-t\) cut in the graph and what is its capacity?

Solution.

\(K(S,T) = 4 + 7 + 9 = 20\).

\(F(S,T) = 4 + 0 - 2 + 2 = 4\).

The min cut is \(S = \{s,w,v\}, T = \{x,t\}\) and its value is \(2 + 5 + 3 = 10\).

It turns out that the flow across the cut is the same for any \(s-t\) cut we choose! It’s just the amount of flow.

Lemma 15.1 Let \(f\) be a flow. Then for any \(s-t\) cut \((S,T)\), we have \(F(S,T) = |f|\).

Proof. Let us start with the cut \(S = V \setminus \{t\}, T = \{t\}\). Here we have \(F(S,T) = |f|\) by definition of the amount of flow: the net amount of flow into \(t\). Now let us consider any \(u \in V, u \neq s, u \neq t\). We will move \(u\) from the “S” part of the cut to the “T” part. But we claim \(F(S,T)\) has not changed: the amount we’ve added is \(\sum_{v \in S} \left(f(v,u) - f(u,v)\right)\) and the amount we’ve subtracted is \(\sum_{v \in T} \left(f(u,v) - f(v,u)\right)\). By the net flow constraint, these add up to zero.

Now we repeat with any other vertex, and so on, and we can create any \(s-t\) cut without changing the amount of flow across the cut.

But we also know that flow across the cut is upper-bounded by the capacity of the cut.

Lemma 15.2 Let \(f\) be a valid flow and \((S,T)\) an \(s-t\) cut. Then \(F(S,T) \leq K(S,T)\).

Proof. We have \(F(S,T) = \sum_{u \in S, v \in T} f(u,v) - f(v,u) \leq \sum_{u,v} f(u,v) \leq \sum_{u,v} c(u,v) = K(S,T)\).

Now we can prove that Ford-Fulkerson is correct.

Theorem 15.1 Let \(f\) be a valid flow and \(G_f\) the residual graph. Then \(f\) is a max flow if and only if there is no path from \(s\) to \(t\) in \(G_f\). Furthermore, in this case, the following cut is a min \(s\)-\(t\) cut: $S = $ the set of vertices reachable from \(s\), and \(T = V \setminus S\).

Proof. If there is a path in \(G_f\), then we can augment the flow along this path, so \(f\) could not be a max flow. On the other hand, suppose there is no path. Let \(S,T\) be defined as in the lemma statement. Then for every edge \((u,v)\) with \(u \in S, v \in T\), we have \(f(u,v) = c(u,v)\), as otherwise \((u,v)\) would be an edge in \(G_f\). And we have \(f(v,u) = 0\) for the same reason. So \(F(S,T) = K(S,T)\).

But we know that, for all possible \(s-t\) cuts \((S',T')\), we have \(K(S,T) = F(S,T) = F(S',T') \leq K(S',T')\). This proves that \((S,T)\) is a min cut. So we know that, for any flow \(f'\), we have \(|f'| \leq K(S,T) = F(S,T) = |f|\). This proves that \(f\) is a max flow.

Corollary 15.1 For any algorithm following the Ford-Fulkerson framework, if it halts, then it is correct.

This corollary follows because FF only halts if there is no path from \(s\) to \(t\) in the residual graph.

Corollary 15.2 (Max-Flow Min-Cut Theorem) In any graph, the max \(s-t\) flow is equal to the min \(s-t\) cut.

The corollary follows because Ford-Fulkerson, assuming it halts, finds a max flow that equals a min cut, every time.

15.2 Using Ford-Fulkerson to find a min cut

Knowing what we now know, finding a min cut in a graph is straightforward:

1. Use a Ford-Fulkerson algorithm to find a maximum flow \(f\).
2. Let \(G_f\) be the residual graph.
3. Let \(S\) = the set of vertices reachable from \(s\) in \(G_f\); we can use e.g. BFS to find this set. Let \(T = V \setminus S\).
4. Return \((S,T)\).

To recap, we know that \((S,T)\) is a min cut because for every edge from \(S\) to \(T\), the flow equals the capacity, and there are no reverse edges with flow (otherwise \(T\) would be reachable), so \(F(S,T) = K(S,T)\).

Exercise 15.2 Here is a graph with a flow. Actually, this flow is already a max flow. Find the min cut by running an iteration of Ford Fulkerson starting from here, drawing the residual flow, and using it to find a min cut.

Solution.

Residual flow:

We have \(S = \{s,v,w\}\) and \(T = \{x,t\}\). The value of the min cut is 10.