Hardness of integer linear feasibility with cyclic support

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.

Integer Maximization over ℓ_p Balls: Hardness and Exact Algorithms
Cinar Ari, Robert Hildebrand
arXiv14 Sep 2026PreprintarXiv licenceFull textOptimisation & controlarXiv
Integer Flows on Cyclic Covers of Graphs
Rong Luo, Yuying Ma, D. Christopher Stephens +1
arXiv21 Oct 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
Semiprime Rigidity and Growth along Powers in Integer-Sided Cyclic Polygons
Felix Huber
arXiv2 Nov 2026PreprintarXiv licenceFull textAlgebra & number theoryarXiv
Linear and non-linear thermal system identification based on the integral of non-integer order — Application to solve inverse heat conduction linear and non-linear problems
Jean-Luc Battaglia
International Journal of Thermal Sciences24 Oct 2026Peer-reviewedLicence not stated7 citedMathematical physicsHAL
Integer linear programming based methods for computing the maximum chordal subgraph of an arbitrary graph
François Clautiaux, Pierre Pesneau
HAL1 Oct 2026PreprintCC BY 4.0Full textGeneral mathematicsHAL

Cite

BibTeX RIS

BibTeX

@misc{summa2026hardness,
  title = {{Hardness of integer linear feasibility with cyclic support}},
  author = {Marco Di Summa},
  howpublished = {arXiv},
  year = {2026},
  month = nov,
  doi = {10.48550/arxiv.2611.08304},
  eprint = {2611.08304},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.08304},
  note = {CC BY-NC-ND 4.0},
}

RIS

TY  - UNPB
TI  - Hardness of integer linear feasibility with cyclic support
AU  - Marco Di Summa
PY  - 2026
DA  - 2026/11/05
PB  - arXiv
DO  - 10.48550/arxiv.2611.08304
UR  - https://arxiv.org/abs/2611.08304
AB  - 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.
ER  -

Abstract

Related

Cite