Krokhin, A. and Marx, D. (2010) 'On the hardness of losing weight.', in ICALP '08 Proceedings of the 35th international colloquium on Automata, Languages and Programming. Berlin, Heidelberg : Springer-Verlag , pp. 662-673. Lecture notes in computer science. (5125).
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.
|Item Type:||Book chapter|
|Keywords:||Constraint satisfaction problem, Local search, Complexity, Fixed-parameter tractability.|
|Full text:||Full text not available from this repository.|
|Publisher Web site:||http://dx.doi.org/10.1007/978-3-540-70575-8_54|
|Date accepted:||No date available|
|Date deposited:||No date available|
|Date of first online publication:||2010|
|Date first made open access:||No date available|
Save or Share this output
|Look up in GoogleScholar|