On the hardness of losing weight

Krokhin, A.; Marx, D.

Abstract

We study the complexity of local search for the Boolean constraint satisfaction problem (CSP), in the following form: given a CSP instance, that is, a collection of constraints, and a solution to it, the question is whether there is a better (lighter, i.e., having strictly less Hamming weight) solution within a given distance from the initial solution. We classify the complexity, both classical and parameterized, of such problems by a Schaefer-style dichotomy result, that is, with a restricted set of allowed types of constraints. Our results show that there is a considerable amount of such problems that are NP-hard, but fixed-parameter tractable when parameterized by the distance.

Citation

Krokhin, A., & Marx, D. (2008, July). On the hardness of losing weight. Presented at Automata, Languages and Programming (ICALP 2008), Reykjavik, Iceland

• Presentation Conference Type: Conference Paper (published)
• Conference Name: Automata, Languages and Programming (ICALP 2008)
• Start Date: Jul 7, 2008
• End Date: Jul 11, 2008
• Publication Date: 2008
• Deposit Date: Dec 18, 2009
• Peer Reviewed: Peer Reviewed
• Issue: 5125
• Pages: 662-673
• Book Title: Automata, Languages and Programming 35th International Colloquium, ICALP 2008 Reykjavik, Iceland, July 7-11, 2008 Proceedings, Part I
• DOI: https://doi.org/10.1007/978-3-540-70575-8_54
• Keywords: Constraint satisfaction problem, Local search, Complexity,; Fixed-parameter tractability.
• Public URL: https://durham-repository.worktribe.com/output/1554952