Exponential Local Search in Bounded-Occurrence MAX-CSP
Abstract
We study the number of improving steps that local search may require for (2,2,r)-MCA (Maximum Constraint Assignment), a bounded-occurrence version of MAX-CSP with valued constraints in which every constraint involves at most two variables, every variable occurs in at most two constraints, and every variable takes one of r values. We consider the flip neighborhood, where two assignments are neighbors if they differ in the value of exactly one variable; moving to such a neighbor is called a flip. Local search repeatedly performs improving flips, that is, flips that strictly increase the objective value, until a local optimum is reached. Our main result is that (2,2,5)-MCA has the all-exp property: there is an infinite family of instances with initial assignments for which every sequence of improving flips ending in a local optimum has length exponential in the number of variables. Thus, on these instances, local search requires exponentially many steps regardless of which improving flip is chosen at each step. This is the first all-exp result for (2,2,r)-MCA for any value of r, and our result extends to every r≥ 5. In contrast, for (2,2,2)-MCA every sequence of improving flips has length at most quadratic in the number of variables~\cite{Kaz2020,KCJ2020}. We give a short, direct proof of this result.
Related
- Generalized Logarithmic Sobolev inequalities on Bounded Domains and exponential decay to Boltzmann states for Nernst--Planck--Navier--Stokes systems
- Bellman--Shoreline Search in Arbitrary Dimension: Exponential Vector Oscillators, Active Memory, Precession, and Effective Computability
- Exponential loss of memory for random Lasota--Yorke convex maps with local average expansion
- Local convexity obstructions for bounded realizations of Teichmüller space
- Rigidity for local holomorphic isometric maps from the complex unit ball to reducible bounded symmetric domains
BibTeX
@misc{heimann2026exponential,
title = {{Exponential Local Search in Bounded-Occurrence MAX-CSP}},
author = {Sophia Heimann and Hung P. Hoang and Stefan Hougardy},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.16898},
eprint = {2610.16898},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.16898},
note = {CC BY-SA 4.0},
}
RIS
TY - UNPB
TI - Exponential Local Search in Bounded-Occurrence MAX-CSP
AU - Sophia Heimann
AU - Hung P. Hoang
AU - Stefan Hougardy
PY - 2026
DA - 2026/10/12
PB - arXiv
DO - 10.48550/arxiv.2610.16898
UR - https://arxiv.org/abs/2610.16898
AB - We study the number of improving steps that local search may require for (2,2,r)-MCA (Maximum Constraint Assignment), a bounded-occurrence version of MAX-CSP with valued constraints in which every constraint involves at most two variables, every variable occurs in at most two constraints, and every variable takes one of r values. We consider the flip neighborhood, where two assignments are neighbors if they differ in the value of exactly one variable; moving to such a neighbor is called a flip. Local search repeatedly performs improving flips, that is, flips that strictly increase the objective value, until a local optimum is reached. Our main result is that (2,2,5)-MCA has the all-exp property: there is an infinite family of instances with initial assignments for which every sequence of improving flips ending in a local optimum has length exponential in the number of variables. Thus, on these instances, local search requires exponentially many steps regardless of which improving flip is chosen at each step. This is the first all-exp result for (2,2,r)-MCA for any value of r, and our result extends to every r≥ 5. In contrast, for (2,2,2)-MCA every sequence of improving flips has length at most quadratic in the number of variables~\cite{Kaz2020,KCJ2020}. We give a short, direct proof of this result.
ER -