2026-08-15T12:48:04Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25158 2026-02-09T08:18:00Z ddc:004 open_access

Complexity of Local Search for CSPs Parameterized by Constraint Difference Anand, Aditya Cohen-Addad, Vincent D'Orsi, Tommaso Gupta, Anupam Lee, Euiwoong Panigrahi, Debmalya Peng, Sijin Constraint Satisfaction Problems Parameterized Local Search Optimization 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)⋅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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Aditya Anand and Vincent Cohen-Addad and Tommaso D'Orsi and Anupam Gupta and Euiwoong Lee and Debmalya Panigrahi and Sijin Peng 2025 Is Part Of LIPIcs, Volume 358, 20th International Symposium on Parameterized and Exact Computation (IPEC 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2025.26 urn:nbn:de:0030-drops-251586 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2025.26 eng https://creativecommons.org/licenses/by/4.0/legalcode