{"id":"arxiv/2611.08304","url":"https://arxiv.org/abs/2611.08304","tags":["math.OC","cs.DM"],"score":0,"title":"Hardness of integer linear feasibility with cyclic support","domain":"math.OC","source":"arxiv","authors":["Marco Di Summa"],"reviews":0,"subject":"math.OC","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-11-05","reactions":{}}