Hardness of integer linear feasibility with cyclic support
math.OC, cs.DM
Submitted: 2026-11-05
Updated: 2026-11-05
License: http://creativecommons.org/licenses/by-nc-nd/4.0/
The gist: 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.
Terminology
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.
Related papers
- An Accelerated Proximal Gradient Method for Bures-Wasserstein Space
- FOMTools: Development and AI-Assisted Code Generation for First-Order Methods
- Lions and Muons: Optimization via Stochastic Frank-Wolfe under Heavy-Tailed Noise
- Dynamic Service Recommendation with Congestion-Dependent Joining: Near-Optimal and Constant-Factor Approximation Algorithms
- Integrating Learning and Optimization for Open Transport Capacity Pooling under Disruption
- Zeroth-Order Gradient Estimators under Decision-Dependent Noise