Integer feasibility remains hard with simple cycle structures

Hardness of integer linear feasibility with cyclic support

Discrete Mathematics

Summary

Figuring out whether certain kinds of equations with whole number solutions can be solved is surprisingly tricky. This paper shows that even when the equations are arranged in a very simple pattern—a cycle where each equation and variable only connects twice—the problem is still very hard to solve. The authors prove this remains true under strict limitations on the numbers used and how the equations are formed. They also explain that because of this, some hoped-for shortcuts or efficient methods for solving these problems are unlikely to exist.

What this means in practice

  • For integer programming designers: Avoid relying on polynomial-time solvability assumptions for integer programs with simple cyclic constraints and small coefficient ranges.
  • For constraint solver developers: Recognize inherent limitations on fixed-parameter algorithms manipulating integer variable bounds based on coefficient sizes and right-hand-side values.

A theory result. No direct application yet.

Authors

Marco Di Summa

Abstract

We prove that integer linear feasibility is strongly $NP$-complete even when the constraint matrix has exactly two nonzero entries in every row and column, with its support forming a single cycle. This holds already for monotone systems (one positive and one negative coefficient in each inequality) with nonzero coefficients of absolute value $2$ or $3$ and right-hand sides in $\{-1,0,1,2\}$. No variable bounds are supplied separately from the system. For systems in which each inequality involves at most two variables, this strengthens known hardness results by restricting all numerical data to fixed finite sets. For systems in which each variable occurs in at most two inequalities, this establishes, to the best of our knowledge, the first $NP$-hardness result for feasibility. We also give negative answers, unless $P=NP$, to questions on polynomial-time solvability of integer programs with bounded coefficients and bounded totally $Δ$-modular treewidth, and on fixed-parameter tractability of integer bound propagation with respect to coefficient and right-hand-side magnitudes.