TR99-038 Authors: Peter Jonsson, Paolo Liberatore

Publication: 25th September 1999 00:45

Downloads: 2904

Keywords:

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.