REVIEW
Hardness of integer linear feasibility with cyclic support
Optimization and Control · Submitted 5 Nov 2026 · 21 references
Pith's verdict: A clean, well-proved hardness result: integer feasibility stays strongly NP-complete on a single cycle with coefficients 2 and 3, and the paper deserves real refereeing.
Why Pith says this
Highlight any text to comment on it.
Referee report
The paper
The paper claims
Integer feasibility is strongly NP-complete for cyclic systems whose nonzero coefficients are only 2 or 3 and whose right-hand sides come from {-1,0,1,2}.
The reading
What carries the argument
The central mechanism is the transfer map. For an inequality $p_i x_i - q_i x_{i+1}\le b_i$ with positive $p_i,q_i$, the map $F_i(z)=\lceil(p_i z-b_i)/q_i\rceil$ gives the smallest value that $x_{i+1}$ can take once $x_i=z$, and composing transfer maps along a block eliminates its intermediate variables. For a cyclic system, Lemma 2 reduces feasibility to the existence of an integer $z$ with $F(z)\le z$, where $F$ is the composed transfer map around the cycle. The encoding is driven by $U(z)=\lceil 3z/2\rceil$: the bit assigned to Boolean variable $v_j$ is $U^j(z)\bmod 2$, and Lemma 3 shows that, modulo $2^H$, this map produces every length-$H$ bit pattern exactly once. Clause gadgets are assembled from the maps $U_a(z)=\lceil(3z-a)/2\rceil$ and $V_c(z)=\lceil(2z-c)/3\rceil$; the transfer map of a clause block satisfies $C_S(z)\ge z$ for every $z$, with equality exactly when the three encoded clause bits are not all equal. Each clause block uses $O(N)$ inequalities, so the full cyclic instance is polynomial in the size of the formula, and concatenating all blocks around the cycle makes $F(z)\ge z$ everywhere, so feasibility forces $F(z)=z$, which means every clause is satisfied.
Extended reading notes
Core claim
The central claim is Theorem 1: Problem Cyclic-IP-Feasibility is NP-complete even when $(p_i,q_i)\in\{(2,3),(3,2)\}$ for every $i$ and $b_i\in\{-1,0,1,2\}$. In the language of matrix sparsity, this means integer linear feasibility is strongly NP-complete when the constraint matrix has exactly two nonzero entries per row and column, its support is a single cycle, every inequality is monotone, and no variable bounds are supplied. The theorem also has two direct consequences: it answers the open column-sparsity feasibility question, and it rules out polynomial time for bounded-coefficient, bounded totally $\Delta$-modular-treewidth integer programs and fixed-parameter tractability for integer bound propagation in the coefficient bound, unless $P=NP$.
Load-bearing premise
The load-bearing premise is Lemma 3: as $z$ ranges over residue classes modulo $2^H$, the parity pattern $(U(z)\bmod 2,\ldots,U^H(z)\bmod 2)$ with $U(z)=\lceil 3z/2\rceil$ must hit every length-$H$ bit string exactly once, so every Boolean assignment has an integer encoding. If some pattern were missed, the clause gadgets would not cover all assignments and the reduction would fail.
Editorial extensions
If this is right
- For integer systems with at most two variables per inequality, strong NP-completeness now holds with all coefficients in $\{\pm2,\pm3\}$ and right-hand sides in $\{-1,0,1,2\}$; in particular, the known polynomial cases such as coefficients $\{1,a\}$ cannot be extended to two distinct absolute values greater than 1 unless $P=NP$.
- For systems with at most two occurrences per variable, feasibility is strongly NP-complete, which resolves the column-sparsity feasibility question and settles the strong-hardness question for optimization.
- The variable-constraint incidence graph being a single cycle is already enough for strong NP-completeness, so the polynomial-time boundary lies exactly between acyclic incidence graphs and one-cycle incidence graphs.
- Unless $P=NP$, bounded coefficients plus bounded totally $\Delta$-modular treewidth do not yield polynomial-time integer programming, and integer bound propagation is not fixed-parameter tractable in the coefficient and right-hand-side bound.
Reading between the lines
- Beyond the paper, the period-doubling encoding is a reusable assignment counter: any decision problem that can expose one bit per iteration of a ceiling-linear map might be reducible to the same kind of constant-coefficient feasibility system.
- The paper's singular-matrix remark leaves an open question that its proof does not answer: since nonsingular cyclic systems are always feasible, all hardness is concentrated in the determinant-zero case, and it is worth testing whether restricting to that case with additional arithmetic constraints restores tractability.
- Beyond the paper, the bound-propagation equivalence suggests a concrete diagnostic: on random small NAE-3SAT instances one can run propagation from wide intervals and compare the stabilized lower endpoints against the satisfiability answer, which would localize any failure of the reduction to a specific step.
Original 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 $\Delta$-modular treewidth, and on fixed-parameter tractability of integer bound propagation with respect to coefficient and right-hand-side magnitudes.
The compiled record
The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
The abstract, sentence by sentence
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 $\Delta$-modular treewidth, and on fixed-parameter tractability of integer bound propagation with respect to coefficient and right-hand-side magnitudes.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | 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. | result 0.89 | 0.96 | 0.94 | asserted 1.00 |
| s1 | 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\}$. | result 0.97 | 0.86 | 0.10 | asserted 1.00 |
| s2 | No variable bounds are supplied separately from the system. | limitation 0.28 | 0.43 | 0.02 | asserted 0.99 |
| s3 | 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. | interpretation 0.77 | 0.75 | 0.07 | asserted 0.99 |
| s4 | 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. | result 0.53 | 0.93 | 0.11 | asserted 0.98 |
| s5 | We also give negative answers, unless $P=NP$, to questions on polynomial-time solvability of integer programs with bounded coefficients and bounded totally $\Delta$-modular treewidth, and on fixed-parameter tractability of integer bound propagation with respect to coefficient and right-hand-side magnitudes. | result 0.91 | 0.92 | 0.08 | asserted 0.98 |
What was examined, and what was not
- arXiv listing abstract v1
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
References
Discussion
Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.