A decomposition theory for matroids. V: Testing of matrix total unimodularity (Q1103625)

We present an \(O((m+n)^ 3)\) algorithm for deciding total unimodularity of any real \(m\times n\) matrix, i.e., for deciding whether or not every square submatrix of the given matrix has determinant O or \(\pm 1\). The algorithm relies on the well-known reduction to the binary case, but from then on is quite different from any method we know of, in particular from the prior algorithm by W. H. Cunningham and J. Edmonds, and the recent algorithm by R. E. Bixby, W. H. Cunningham and A. Rajan, which are of order \(O((m+n)^ 5)\) and \(O((m+n)^{4.5}(\log (m+n))^{0.5})\), respectively. The most difficult part of the algorithm, where regularity of a 3- connected, binary, nongraphic and noncographic matroid must be decided, is handled by a search procedure that relies on the concept of induced decompositions of Parts III and IV. The efficacy of that search procedure crucially depends on asymmetries between certain circuit results and cocircuit results of graphs. In other settings these asymmetries can be quite annoying, but here they turn out to be most beneficial.