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. (online). On the hardness of losing weight. https://doi.org/10.1007/978-3-540-70575-8_54

• Journal Article Type: Article
• Deposit Date: Dec 18, 2009
• Peer Reviewed: Peer Reviewed
• Issue: 5125
• Pages: 662-673
• 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