## On the Complexity of Finding Satisfiable Subinstances in
Constraint Satisfaction

**Peter Jonsson and Paolo Liberatore**
*Technical Report, Electronic Colloquium on Computational
Complexity*

We study the computational complexity of an optimization version
of the constraint satisfaction problem: given a set F of
constraint functions, an instance consists of a set of variables
V related by constraints chosen from F and a natural number k.
The problem is to decide whether there exists a subset V' of V
such that the size of V' is greater or equal than k and the
subinstance induced by V' has a solution. For all possible
choices of F, we show that this problem is either NP-hard or
trivial. This hardness result makes it interesting to study
relaxations of the problem which may have better computational
properties. Thus, we study the approximability of the problem
and we consider certain compilation techniques. In both cases,
the results are not encouraging.

@techreport{jons-libe-99,
title = {On the Complexity of Finding Satisfiable Subinstances in
Constraint Satisfaction},
year = {1999},
author = {Jonsson, Peter and Liberatore, Paolo},
institution = {Electronic Colloquium on Computational
Complexity},
number = {TR99-038},
}

FTP
download.