On Matrices over a Polynomial Ring with Restricted Subdeterminants

This paper introduces a framework to study discrete optimization problems which are parametric in the following sense: their constraint matrices correspond to matrices over the ring \(\mathbb {Z}[x]\) of polynomials in one variable. We investigate in particular matrices whose subdeterminants all lie in a fixed set \(S\subseteq \mathbb {Z}[x]\) . Such matrices, which we call totally S-modular matrices, are closed with respect to taking submatrices, so it is natural to look at minimally non-totally S-modular matrices which we call forbidden minors for S. Among other results, we prove that if S is finite, then the set of all determinants attained by a forbidden minor for S is also finite. Specializing to the integers, we subsequently obtain the following positive complexity results: the recognition problem for totally \(\pm \{0,1,a,a+1,2a+1\}\) -modular matrices with \(a\in \mathbb {Z}\backslash \lbrace -3,-2,1,2\rbrace \) and the integer linear optimization problem for totally \(\pm \lbrace 0,a,a+1,2a+1\rbrace \) -modular matrices with \(a\in \mathbb {Z}\backslash \lbrace -2,1\rbrace \) can be solved in polynomial time.