On a Class of Totally Unimodular Matrices

Abstract

We examine the class of totally unimodular matrices-that contain no odd cycles, which we call restricted totally unimodular (RTUM). We show that a matrix is RTUM if and only if it can be decomposed in a very simple way into the incidence matrices (or their transposes) of bipartite graphs or directed graphs, and give a linear time algorithm to perform this task. Based on this decomposition, we show that the 0,1 Integer Programming Problem with an RTUM matrix of constraints has the same time complexity as the b-matching and the max flow problems.