ECCC-Report TR99-038https://eccc.weizmann.ac.il/report/1999/038Comments and Revisions published for TR99-038en-usSat, 25 Sep 1999 00:45:22 +0200
Paper TR99-038
| On the Complexity of Finding Satisfiable Subinstances in Constraint Satisfaction |
Peter Jonsson,
Paolo Liberatore
https://eccc.weizmann.ac.il/report/1999/038We 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.
Sat, 25 Sep 1999 00:45:22 +0200https://eccc.weizmann.ac.il/report/1999/038