Metraipolis › archive › dc_ad55dc16023a
Hardness of integer linear feasibility with cyclic support — arXiv:2611.08304
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.08304
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-06T14:52:03.809Z
- SHA-256 of the archived text
5ca1bb3262a1b05800f3d5f3a9da76bb67a43326bcdf84590b4cdfa633069c05- Stable URL of this page
https://metraipolis.com/documento/dc_ad55dc16023a
How to cite
Hardness of integer linear feasibility with cyclic support — arXiv:2611.08304 — arXiv (en), https://arxiv.org/abs/2611.08304 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_ad55dc16023a (Metraipolis archive dc_ad55dc16023a, sha256 5ca1bb3262a1b05800f3d5f3a9da76bb67a43326bcdf84590b4cdfa633069c05)
BibTeX
@misc{dcad55dc16023a,
title = {Hardness of integer linear feasibility with cyclic support — arXiv:2611.08304},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.08304},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_ad55dc16023a; sha256 5ca1bb3262a1b05800f3d5f3a9da76bb67a43326bcdf84590b4cdfa633069c05},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.08304. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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.
Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.OC, nuovi lavori del giorno).
Categorie arXiv: Optimization and Control (math.OC) ; Discrete Mathematics (cs.DM).
Pagina del lavoro: https://arxiv.org/abs/2611.08304 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-06T14:23:27.653Z dalla pagina https://arxiv.org/list/math.OC/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).