{"ID":2834207,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2512.03275","arxiv_id":"2512.03275","title":"Complexity of Local Search for CSPs Parameterized by Constraint Difference","abstract":"In this paper, we study the parameterized complexity of local search, whose goal is to find a good nearby solution from the given current solution. Formally, given an optimization problem where the goal is to find the largest feasible subset $S$ of a universe $U$, the new input consists of a current solution $P$ (not necessarily feasible) as well as an ordinary input for the problem. Given the existence of a feasible solution $S^*$, the goal is to find a feasible solution as good as $S^*$ in parameterized time $f(k) \\cdot n^{O(1)}$, where $k$ denotes the distance $|PΔS^*|$. This model generalizes numerous classical parameterized optimization problems whose parameter $k$ is the minimum number of elements removed from $U$ to make it feasible, which corresponds to the case $P = U$. We apply this model to widely studied Constraint Satisfaction Problems (CSPs), where $U$ is the set of constraints, and a subset $U'$ of constraints is feasible if there is an assignment to the variables satisfying all constraints in $U'$. We give a complete characterization of the parameterized complexity of all boolean-alphabet symmetric CSPs, where the predicate's acceptance depends on the number of true literals.","short_abstract":"In this paper, we study the parameterized complexity of local search, whose goal is to find a good nearby solution from the given current solution. Formally, given an optimization problem where the goal is to find the largest feasible subset $S$ of a universe $U$, the new input consists of a current solution $P$ (not n...","url_abs":"https://arxiv.org/abs/2512.03275","url_pdf":"https://arxiv.org/pdf/2512.03275v1","authors":"[\"Aditya Anand\",\"Vincent Cohen-Addad\",\"Tommaso d'Orsi\",\"Anupam Gupta\",\"Euiwoong Lee\",\"Debmalya Panigrahi\",\"Sijin Peng\"]","published":"2025-12-02T22:28:11Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}