Archive for October, 2009

Total unimodularity and networks

12 October, 2009

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 A is called totally unimodular if each of its subdeterminants equals 0, 1, or -1. (In particular, each entry of A is 0, 1, or -1.)

Proposition. Let A be totally unimodular and b\in\mathbb{Z}^n. Then the polyhedron P=\{x\mid Ax\leq b\} is integral (i.e. each face has an integer point.)

Proof. For a minimal (w.r.t. inclusion) face F of P one has F=\{x\mid A'x=b'\}, where A', resp. b' is a submatrix, resp. subvector, of A, resp. of b, and A' has full row rank. Then, possibly after permuting coordinates, we have A'=(U; V), with |U|\neq 0. By total unimodularity, |U|=\pm 1. Then x:=(U^{-1}b'\ 0)\in \mathbb{Z}^m and satisfies A'x=b'.

To complete the proof we need to check that x\in P. This is where the minimality of F is needed. In the simplest case F is a vertex, and \{x\}=F, implying the claim. In general, F=v+Null(A), i.e. a translate of the nullspace of A. So one can reduce to the vertex case by adding equations of the form x_j=0 for each column j of the submatrix V; this does not destroy the feasibility of Ax\leq b. QED.

As a corollary, the LP \max_{x\in P} c^T x has integer optimum (and optimiser) whenever c\in \mathbb{Z}^m. Moreover, the same holds for its LP dual \min b^T y, y\in P^*=\{z\geq 0\mid A^Tz=c\}, by rewriting P^*=\{z\mid (I;A^T;-A^T)z\leq (\overline{0},c,-c) and applying the proposition above.

Hoffman-Kruskal Theorem. It turns out that this property characterises
total unimodularity:

  1. A is totally unimodular iff for any b\in\mathbb{Z}^n the polyhedron P=\{x\mid Ax\leq b\} is integral.
  2. A is totally unimodular iff for any b\in\mathbb{Z}^n, c\in\mathbb{Z}^m the equality in the LP duality equation \max_{x\in P} c^T x=\min_{y\in P^*}b^T y 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 A' is totally unimodular iff for any b'\in\mathbb{Z}^{n'} the polyhedron \{x\mid x\geq 0, A'x=b'\} is integral.

We omit the proof here.

Examples of totally unimodular matrices.

(Vertex-edge) incidence matrix A of a graph \Gamma=(V,E) is totally unimodular iff \Gamma 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 (1,2), (2,3),\dots,(n-1,n),(1,n) and arranging the columns of the matrix in this order, while arranging the rows in the order 2,3,\dots,n-1,n,1. Then the usual decomposition of the determinant w.r.t. all the permutations of n symbols will have only 2 nonzero summands, that will not cancel each other (actually, in the case of n even they will cancel each other).
This shows that A cannot be totally unimodular if \Gamma is not bipartite.
2) Let A' be a square submatrix of A. 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 A. This leaves one with the case of A' having exactly two 1s per column. Same argument can be applied to argue that A' has, w.l.o.g., at least two 1s per row, and thus exactly two 1s, by counting 1s of A' in two ways. It follows that A' is the incidence matrix of a disjoint union of (even, as \Gamma is bipartite) cycles. By reordering the rows and columns we and make A' 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 M of a digraph \Gamma=(V,A) is a 0,1,-1 matrix of size |V|\times |A| so that A_{v,d}=0,1,-1 if, respectively, d\in A misses v\in V, or d arrives to v, or d leaves v. Show that A 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 \Gamma=(V,A) with two marked nodes s,t\in V, and arc capacities c: A\to \mathbb{R}_+. An s-tflow on the network (\Gamma,s,t,c) is a function f: A\to \mathbb{R}_+ satisfying f(a)\leq c(a) for all a\in A and f_+(v)=f_-(v) for any v\in V\setminus\{s,t\}, where f_+=\sum_{u\in V\mid (uv)\in A} f(uv), and f_-=\sum_{u\in V\mid (vu)\in A} f(vu). (The latter is called conservation law.) The value of f is f_+(s)-f_-(s), i.e. the “amount” of f that “leaves” s.
And s-t cut is a partition of V into two parts S and T so that s\in S, t\in T. The capacity of the cut is the sum of the capacities of the arc leaving T.

Max-flow min-cut theorem. Given the network (\Gamma,s,t,c), the maximum value of an s-t-flow is equal to the minimum capacity of an s-t-cut.

In order to formulate this as an LP, we introduce the function w:A\to \mathbb{Z}_+ so that w(a)=0,1,\text{ or }-1 if, respectively, a misses s, or resp. a enters s, or resp. a leaves s. Now we can formulate the max-flow problem as follows:

\max \sum_{a\in A} w(a)f(a)\quad\text{subject to}\\ 0\leq f(a)\leq c(a), \text{ for } a\in A,\\ f_+(v)=f_-(v)\text{ for } v\in V\setminus\{s,t\}.

Let M' be the sumbatrix of the incidence matrix M of \Gamma obtained by removing the rows with indices s and t. Then the latter can be rewritten as

\max w^T f\mid 0\leq f\leq c,\ M'f=0.

The matrix of this LP is totally unimodular. If c:A\to \mathbb{Z}_+ 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:

\min y^T c \mid y\geq 0, y^T+z^T M'\geq w^T.

Here the minimum is attained by integer vectors, as the polytope describing the feasible set is integral. We can extend z by defining z_s:=-1, z_t:=0. Then y^T+z^T M\geq 0. The set U:=\{v\in V| z_v\geq 0\} satisfies t\in U, s\not\in U. So it is a cut. To show the claim of the theorem, it suffices to show that the total capacity of the arcs leaving U is bounded from above (the opposite direction is easy) by y^T c=\text{maxflow}. Let a=(u,v) is such an arc. Then z_u\geq 0 and z_v\leq -1. Then y^T+z^T M\geq 0 implies v_a+z_u-z_v\geq 0, so y_a\geq 1. Q.E.D.