0/1 integer programming over polytopes of Chvátal rank one is as hard as lattice problems
Abstract
A rational polyhedron has Chvátal rank at most one if a single round of Chvátal-Gomory cuts yields its integer hull. In 1973, Chvátal asked whether 0/1 integer programs over polytopes of bounded Chvátal rank can be solved in polynomial time. For polyhedra of bounded Chvátal rank, integer feasibility is in NP ∩ coNP, so it is unlikely to be NP-hard. We answer Chvátal's question negatively already in its most restricted form: for Chvátal rank one, for integer feasibility, and even for the SAT polytopes of formulas whose clauses have at most three literals. Our answer holds under either of two standard assumptions from lattice-based cryptography. First, a polynomial-time algorithm for integer feasibility on such SAT polytopes of Chvátal rank one would solve bounded distance decoding with polynomial factors in deterministic polynomial time, contradicting the conjectured hardness of approximating lattice problems within polynomial factors. Second, assuming the hardness of learning with errors, an average-case analog of bounded distance decoding, the problem is also hard on average, for a polynomial-time samplable distribution of formulas. This also gives negative answers to related questions of Cornuéjols, Lee, and Li. We first prove these results for parallelepipeds, where they rest on an elementary sufficient condition: a polyhedron has Chvátal rank at most one if its width is less than one along every row of some unimodular matrix. For our parallelepipeds, such a matrix exists but is hard to find. For SAT polytopes, we represent candidate lattice vectors by their residues modulo small integers, and binary arithmetic on additional 0/1 variables checks that these vectors lie in the lattice.
Related
- A quadratic upper bound on the Chvátal rank of polytopes in the 0/1-cube
- On the Chvátal-Gomory Closure of Integer Quadratic Programs
- Integer decomposition property of three-dimensional smooth polytopes: a shorter proof
- Integer linear programming based methods for computing the maximum chordal subgraph of an arbitrary graph
- Hidden Convexity via Symmetric Displacement Covers: Mixed-Integer Quadratic Programming and Integer Cubic Programming in Fixed Dimension
BibTeX
@misc{pia2026integer,
title = {{0/1 integer programming over polytopes of Chvátal rank one is as hard as lattice problems}},
author = {Alberto Del Pia},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.10911},
eprint = {2610.10911},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.10911},
}
RIS
TY - UNPB
TI - 0/1 integer programming over polytopes of Chvátal rank one is as hard as lattice problems
AU - Alberto Del Pia
PY - 2026
DA - 2026/10/24
PB - arXiv
DO - 10.48550/arxiv.2610.10911
UR - https://arxiv.org/abs/2610.10911
AB - A rational polyhedron has Chvátal rank at most one if a single round of Chvátal-Gomory cuts yields its integer hull. In 1973, Chvátal asked whether 0/1 integer programs over polytopes of bounded Chvátal rank can be solved in polynomial time. For polyhedra of bounded Chvátal rank, integer feasibility is in NP ∩ coNP, so it is unlikely to be NP-hard. We answer Chvátal's question negatively already in its most restricted form: for Chvátal rank one, for integer feasibility, and even for the SAT polytopes of formulas whose clauses have at most three literals. Our answer holds under either of two standard assumptions from lattice-based cryptography. First, a polynomial-time algorithm for integer feasibility on such SAT polytopes of Chvátal rank one would solve bounded distance decoding with polynomial factors in deterministic polynomial time, contradicting the conjectured hardness of approximating lattice problems within polynomial factors. Second, assuming the hardness of learning with errors, an average-case analog of bounded distance decoding, the problem is also hard on average, for a polynomial-time samplable distribution of formulas. This also gives negative answers to related questions of Cornuéjols, Lee, and Li. We first prove these results for parallelepipeds, where they rest on an elementary sufficient condition: a polyhedron has Chvátal rank at most one if its width is less than one along every row of some unimodular matrix. For our parallelepipeds, such a matrix exists but is hard to find. For SAT polytopes, we represent candidate lattice vectors by their residues modulo small integers, and binary arithmetic on additional 0/1 variables checks that these vectors lie in the lattice.
ER -