Let $A in mathbb{Z}^{m times n}$ be an integral matrix and $a$, $b$, $c in mathbb{Z}$ satisfy $a geq b geq c geq 0$. The question is to recognize whether $A$ is ${a,b,c}$-modular, i.e., whether the set of $n times 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 times n$ subdeterminants $k_1$ and $k_2$ satisfying $2 cdot |k_1| = |k_2|$. 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$.
تحميل البحث