On the Complexity of Finding Satisfiable Subinstances in Constraint Satisfaction

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},
 }