Limitations of Affine Integer Relaxations for Solving Constraint Satisfaction Problems
<|reference_start|>Limitations of Affine Integer Relaxations for Solving Constraint Satisfaction Problems: We show that various known algorithms for finite-domain constraint satisfaction problems (CSP), which are based on solving systems of linear equations over the integers, fail to solve all tractable CSPs correctly. The algorithms include $\mathbb{Z}$-affine $k$-consistency, BLP+AIP, every fixed level of the BA$^{k}$-hierarchy, and the CLAP algorithm. In particular, we refute the conjecture by Dalmau and Opr\v{s}al that there is a fixed constant $k$ such that the $\mathbb{Z}$-affine $k$-consistency algorithm solves all tractable finite domain CSPs.<|reference_end|>
@article{lichter2024limitations,
    title={Limitations of Affine Integer Relaxations for Solving Constraint
  Satisfaction Problems},
    author={Moritz Lichter, Benedikt Pago},
    journal={arXiv preprint arXiv:2407.09097},
    year={2024},
    archivePrefix={arXiv},
    eprint={2407.09097},
    primaryClass={cs.CC}
}