The Max Flow-Min Cut Theorem states that the maximum flow from the source node to the sink node through a capacitated network is equal to the capacity of the minimum cut that separates that source node from the sink node. In this post we’ll show that this result, which can be proved using only network concepts, also follows from the strong duality theorem for linear programming.
Here’s a linear programming formulation of the maximum flow problem.
Here, f is the total amount of flow, is the amount of flow sent along arc , A is the set of arcs, N is the set of nodes, s is the (single) source, t is the (single) sink, and is the capacity (upper bound) of arc .
The constraints involving the summations are the flow-balance constraints. They enforce the idea that the total amount of flow into a node must equal the total amount of flow out of that node. The two exceptions are the source and the sink, which emit and absorb, respectively, all the flow through the network.
The dual of this problem is
Here, is the dual variable associated with the upper bound constraint on arc , and is the dual variable associated with the flow-balance constraint on node i.
Next, let’s take a look at why the dual problem corresponds to the problem of finding a minimum cut. In a search for an optimal solution we will want to set as much as possible. This means that we will want to set for as many arcs as possible. (*) However, we cannot set for all arcs , as the requirement means will have a value one unit larger than . So in a search for an optimal solution to the dual we can consider only those cases in which we break the node set into two pieces: Those nodes i satisfying and those nodes j satisfying . Thus this set of cases in which the optimal solution must be found corresponds to the set of cuts that place the source and sink in different subsets.
Does this set of cases leave out any cuts, though? No. To see this, note that every cut with corresponds to a feasible solution to the dual in the following manner. Let . Then let
This assignment satisfies the dual problem, and its corresponding objective function value is exactly the capacity of the cut .
Since the assignment of zero flow through the network is feasible for the original problem, both the original problem and its dual are feasible. By the strong duality theorem, then, the original problem and its dual have optimal solutions whose objective function values are equal. Therefore, the maximum flow through the network must equal the capacity of the minimum cut that separates the source node s from the sink node t.
(*) Well, the constraint actually just requires , but we know from complementary slackness that if there’s positive flow on an arc in the optimal solution to the maximum flow problem then the corresponding dual constraint must be satisfied at equality. So for the dual constraints that actually constrain the solution and thus actually matter we’ll have in the dual optimal.