Notes on $\{a,b,c\}$Modular Matrices
Abstract
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 wellknown 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$.
 Publication:

arXiv eprints
 Pub Date:
 June 2021
 arXiv:
 arXiv:2106.14980
 Bibcode:
 2021arXiv210614980G
 Keywords:

 Mathematics  Optimization and Control;
 Computer Science  Computational Complexity;
 Computer Science  Data Structures and Algorithms;
 90C10;
 68Q25
 EPrint:
 This version of the article has been accepted for publication after peer review but is not the Version of Record and does not reflect postacceptance improvements, or any corrections. The Version of Record is available online at: https://doi.org/10.1007/s10013021005209