Advances on strictly \(\Delta \)-modular IPs

There has been significant work recently on integer programs (IPs) \(\min \{c^\top x :Ax\le b,\,x\in \mathbb {Z}^n\}\) $min\{c^{\top }x:Ax\le b,x\in {\mathbb{Z}}^n\}$ with a constraint marix A with bounded subdeterminants. This is motivated by a well-known conjecture claiming that, for any constant \(\Delta \in \mathbb {Z}_{>0}\) $\mathrm{\Delta }\in {\mathbb{Z}}_{>0}$ , \(\Delta \) $\mathrm{\Delta }$ -modular IPs are efficiently solvable, which are IPs where the constraint matrix \(A\in \mathbb {Z}^{m\times n}\) $A\in {\mathbb{Z}}^{m\times n}$ has full column rank and all \(n\times n\) $n\times n$ minors of A are within \(\{-\Delta , \dots , \Delta \}\) $\{-\mathrm{\Delta },\cdots ,\mathrm{\Delta }\}$ . Previous progress on this question, in particular for \(\Delta =2\) $\mathrm{\Delta }=2$ , relies on algorithms that solve an important special case, namely strictly \(\Delta \) $\mathrm{\Delta }$ -modular IPs, which further restrict the \(n\times n\) $n\times n$ minors of A to be within \(\{-\Delta , 0, \Delta \}\) $\{-\mathrm{\Delta },0,\mathrm{\Delta }\}$ . Even for \(\Delta =2\) $\mathrm{\Delta }=2$ , such problems include well-known combinatorial optimization problems like the minimum odd/even cut problem. The conjecture remains open even for strictly \(\Delta \) $\mathrm{\Delta }$ -modular IPs. Prior advances were restricted to prime \(\Delta \) $\mathrm{\Delta }$ , which allows for employing strong number-theoretic results. In this work, we make first progress beyond the prime case by presenting techniques not relying on such strong number-theoretic prime results. In particular, our approach implies that there is a randomized algorithm to check feasibility of strictly \(\Delta \) $\mathrm{\Delta }$ -modular IPs in strongly polynomial time if \(\Delta \le 4\) $\mathrm{\Delta }\le 4$ .