Total unimodularity is a tool to show that a linear programming problem (LP) has integer optimal solutions. In our discussion on bipartite matchings and linear programming we saw how this is possible to do by hand in a particular case, but as the structure of the LP gets more complicated the details can get very messy. Fortunately, there is a general tool that sometimes gives what is needed.

Definition. A matrix is calledtotally unimodularif each of its subdeterminants equals 0, 1, or -1. (In particular, each entry of is 0, 1, or -1.)

Proposition.Let be totally unimodular and Then the polyhedron is integral (i.e. each face has an integer point.)

**Proof.** For a minimal (w.r.t. inclusion) face of one has where resp. is a submatrix, resp. subvector, of resp. of and has full row rank. Then, possibly after permuting coordinates, we have with By total unimodularity, Then and satisfies

To complete the proof we need to check that This is where the minimality of is needed. In the simplest case is a vertex, and implying the claim. In general, i.e. a translate of the nullspace of So one can reduce to the vertex case by adding equations of the form for each column of the submatrix this does not destroy the feasibility of QED.

As a corollary, the LP has integer optimum (and optimiser) whenever Moreover, the same holds for its LP dual by rewriting and applying the proposition above.

**Hoffman-Kruskal Theorem.** It turns out that this property characterises

total unimodularity:

- is totally unimodular iff for any the polyhedron is integral.
- is totally unimodular iff for any , the equality in the LP duality equation is achieved by integral vectors (assuming these min and max are finite).

The second obviously follows from the first.

The first will follow from the following:

A full rank matrix is totally unimodular iff for any the polyhedron is integral.

We omit the proof here.

**Examples of totally unimodular matrices.**

(Vertex-edge) incidence matrix of a graph is totally unimodular iff is bipartite.

**Sketch of the proof.**

1) Prove that the incidence matrix of an odd cycle is not totally unimodular, e.g. by considering the vertex numbering such that the edges are and arranging the columns of the matrix in this order, while arranging the rows in the order Then the usual decomposition of the determinant w.r.t. all the permutations of symbols will have only 2 nonzero summands, that will not cancel each other (actually, in the case of even they will cancel each other).

This shows that cannot be totally unimodular if is not bipartite.

2) Let be a square submatrix of If it has a 0 column its determinant is 0. If it has a column with just one 1, we can decompose the determinant w.r.t. this column and apply induction on the size of This leaves one with the case of having exactly two 1s per column. Same argument can be applied to argue that has, w.l.o.g., at least two 1s per row, and thus exactly two 1s, by counting 1s of in two ways. It follows that is the incidence matrix of a disjoint union of (even, as is bipartite) cycles. By reordering the rows and columns we and make to be block-diagonal, with each block the incidence matrix of an even cycle. The determinant of a block-diagonal matrix equals the product of determinants of the blocks, and so it remains to show that the incidence matrix of an even cycle is totally unimodular; this can be done as above. Q.E.D.

Excercise.Combine this with the result on the total unimodularity above to show that the maximum matching LP for bipartite graphs has an integer solution. Construct the LP dual for this problem and interpret its integer solutions (show that they exist first!) in graph-theoretic terms.

Excercise.The incidence matrix of a digraph is a 0,1,-1 matrix of size so that if, respectively, misses or arrives to or leaves Show that is totally unimodular.

**Network flows and max-flow min-cut theorem.**

Armed with the above, we can easily prove the max-flow min-cut theorem for networks. Recall that a *network* is a directed graph with two marked nodes and arc *capacities* An –*flow* on the network is a function satisfying for all and for any where and (The latter is called *conservation law*.) The *value* of is i.e. the “amount” of that “leaves”

And *cut* is a partition of into two parts and so that The *capacity of the cut* is the sum of the capacities of the arc leaving

Max-flow min-cut theorem.Given the network the maximum value of an -flow is equal to the minimum capacity of an -cut.

In order to formulate this as an LP, we introduce the function so that if, respectively, misses or resp. enters or resp. leaves Now we can formulate the max-flow problem as follows:

Let be the sumbatrix of the incidence matrix of obtained by removing the rows with indices and Then the latter can be rewritten as

The matrix of this LP is totally unimodular. If then we can apply the integrality result directly, and establish along the way that there exists an optimal integral flow. In general, we cannot apply the unimodularity directly. But we can take the LP dual. It is as follows:

Here the minimum is attained by *integer* vectors, as the polytope describing the feasible set is integral. We can extend by defining Then The set satisfies So it is a cut. To show the claim of the theorem, it suffices to show that the total capacity of the arcs leaving is bounded from above (the opposite direction is easy) by Let is such an arc. Then and Then implies so Q.E.D.

Tags: combinatorics, graph theory, MAS324, MAS445

11 October, 2010 at 0:17 |

[…] discussed how to formulate the MAXFLOW problem for networks, i.e. arc-weighted digraphs with two specific […]

2 January, 2011 at 22:01 |

[…] Total unimodularity and networks October 20091 comment 3 […]