Notes on {a,b,c}-Modular Matrices

Let A ∈ Zm×n be an integral matrix and a, b, c ∈ Z satisfy a ≥ b ≥ c ≥ 0. The question is to recognize whether A is {a, b, c}-modular, i.e., whether the set of n×n subdeterminants of A in absolute value is {a, b, c}. We will succeed in solving this problem in polynomial time unless A possesses a duplicative relation, that is, A has nonzero n × n subdeterminants k1 and k2 satisfying 2·|k1|=|k2|. This is an extension of the well-known recognition algorithm for totally unimodular matrices. As a consequence of our analysis, we present a polynomial time algorithm to solve integer programs in standard form over {a, b, c}-modular constraint matrices for any constants a, b and c.ISSN:2305-2228ISSN:0866-7179ISSN:2305-221