Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR99-038 | 27th August 1999 00:00

On the Complexity of Finding Satisfiable Subinstances in Constraint Satisfaction


Authors: Peter Jonsson, Paolo Liberatore
Publication: 25th September 1999 00:45
Downloads: 3408


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' \subseteq V$ such
that $|V'| \geq 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.

ISSN 1433-8092 | Imprint