Paperlane

no. 17 · Wednesday 18 November 2026

Binary Affine Optimization with Nearly-Graphic Constraint Matrices

Qiming Fang, Sihong Shao and Yuxuan Wu

math.OC · via cs.DS · 25 pp

Abstract

We present a polynomial-time algorithm for binary affine optimization with a linear objective when every column of the constraint matrix has Hamming weight at most 2, and prove that the problem is NP-hard when every column of the constraint matrix has Hamming weight exactly 3. We obtain fixed-parameter tractable (FPT) algorithms for the unrestricted problem provided that a nearly-graphic certificate is given, where the certificate roughly measures how far the constraint matrix is from having columns of Hamming weight at most 2. We apply our FPT algorithm to Max-Lin$_2$ on graphs and obtain FPT algorithms parameterized by the contraction distance and contraction rank of the graph, utilizing the concept of Eulerian-spanning set. In the case of contraction distance, another FPT algorithm can be used to find the corresponding certificate; that is, we obtain an FPT algorithm that requires no information beyond the problem instance itself.

comments
25 Pages, 5 Figures
fields
Optimization and Control
pdf ↗ page arXiv:2611.22944 ↗