Max-Flow Min-Cut with Linear Programming
by potatio, Jan 22, 2020, 7:23 PM
This work is based on Totally Unimodular Matrices. However, they use a different notation there, so I just wanted to rewrite their proof in my own words.
Define the incidence matrix
of a directed graph
as:
Thus, the dimensions of
are
.
Now, let's move on to flows. Let
be the capacity vector with all non-negative integer entries.
Let the row in
corresponding to the source vertex
be
. Let
be
with rows corresponding to
and
removed.
Then, maximum flow can be written as the primal linear program:
Then, the dual linear program corresponds to:

is actually a vector of size
. It has one variable for each vertex that is not
nor
. This is inconvenient, so we add
and
.
This changes the first dual constraint to
.
Now, we need some facts (that will not be proven here but these proofs are available in the link above):
Note that for an LP, a vertex of the feasible region must be in the optimal solution set (think of the gradient of the objective function and how it 'pulls').This shows that an optimal flow exists with integer values if all capacities are integers!
Thus, we can consider the optimal solutions of the primal and dual to be occurring at vertices of the respective feasible regions. Let
and
be the integer-valued optimal solutions respectively.
We have, looking at the constraint in the dual for edge
, and the feasibility condition,
As the dual is a minimization problem, and
, it will always be optimal to choose equality in the above inequality. However, we will not need this fact directly.
We need to relate these variables in the dual to a
cut separating
and
.
Define
. Then,
and
, so this is a valid
cut.
Consider an edge
crossing this cut. As
are all integers, the above gives (with the definition of
and
):
Thus, the optimal value of the dual is
which is the optimal value of the primal.
But, we know that these optimal values are the same! Hence, we must have equality everywhere. This means:
![\[
d_{ij} = \begin{cases}
1, & \text{if } i \in S \text{ and } j \in T \\
0, & \text{otherwise} \\
\end{cases}
\]](//latex.artofproblemsolving.com/4/a/f/4af49cc18e347dcdbe2f161f2e2bda8cf334afe2.png)
![\[
z_{i} = \begin{cases}
-1, & \text{if } i \in S \\
0, & \text{otherwise} \\
\end{cases}
\]](//latex.artofproblemsolving.com/e/4/2/e42d3b3910675c15485a21424c8fec1fd4d024b1.png)
Define the incidence matrix


![\[
A_{ij} = \begin{cases}
1, & \text{if edge } j \text{ originates at vertex } i \\
-1, & \text{if edge } j \text{ ends at vertex } i \\
0, & \text{otherwise} \\
\end{cases}
\]](http://latex.artofproblemsolving.com/4/f/0/4f08a3d62f1526ddabc47ef4887d4abafed127a1.png)


Now, let's move on to flows. Let

Let the row in







Then, maximum flow can be written as the primal linear program:








This changes the first dual constraint to

Now, we need some facts (that will not be proven here but these proofs are available in the link above):
- A matrix
is said to be totally unimodular if every square submatrix of
has determinant
or
.
- A non-singular submatrix of a totally unimodular matrix
has an integer inverse.
- The vertices of the convex polytope
where
has integer entries have all integer entries too.
is totally unimodular for any graph
.
Note that for an LP, a vertex of the feasible region must be in the optimal solution set (think of the gradient of the objective function and how it 'pulls').This shows that an optimal flow exists with integer values if all capacities are integers!
Thus, we can consider the optimal solutions of the primal and dual to be occurring at vertices of the respective feasible regions. Let


We have, looking at the constraint in the dual for edge

![\[
d^*_{uv} \geq \max(0, z^*_v - z^*_u).
\]](http://latex.artofproblemsolving.com/f/f/a/ffa1f8b7c8997b7f957e1aa12e76c90fd6298387.png)

We need to relate these variables in the dual to a



Define




Consider an edge




![\[
d^*_{uv} \geq 1.
\]](http://latex.artofproblemsolving.com/1/1/b/11bbd1baf0d773380fa48f5d9831e4f9c733bc6d.png)
![\[
c^Td^* \geq \sum_{e \text{ crossing } } c_e = \text{ capacity of } s-t \text{ cut }\geq \text{ maximum flow out of } S = w^Tx^*,
\]](http://latex.artofproblemsolving.com/5/7/e/57e8f394025f07cefcb4d2606494bc0e8cf36257.png)
But, we know that these optimal values are the same! Hence, we must have equality everywhere. This means:
![\[
d_{ij} = \begin{cases}
1, & \text{if } i \in S \text{ and } j \in T \\
0, & \text{otherwise} \\
\end{cases}
\]](http://latex.artofproblemsolving.com/4/a/f/4af49cc18e347dcdbe2f161f2e2bda8cf334afe2.png)
![\[
z_{i} = \begin{cases}
-1, & \text{if } i \in S \\
0, & \text{otherwise} \\
\end{cases}
\]](http://latex.artofproblemsolving.com/e/4/2/e42d3b3910675c15485a21424c8fec1fd4d024b1.png)
This post has been edited 9 times. Last edited by potatio, Jan 23, 2020, 8:45 AM