Skip to main content

Research Repository

Advanced Search

On the hardness of losing weight

Krokhin, A.; Marx, D.

Authors

D. Marx



Contributors

L. Aceto
Editor

I. Damgard
Editor

L.A. Goldberg
Editor

M.M. Halldorsson
Editor

A. Ingolfsdottir
Editor

I. Walukiewicz
Editor

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

Journal Article Type Article
Publication Date Jan 1, 2010
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.


You might also like



Downloadable Citations