Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR03-062 | 10th July 2003 00:00

Recognizing Frozen Variables in Constraint Satisfaction Problems

RSS-Feed




TR03-062
Authors: Andrei Krokhin, Peter Jonsson
Publication: 8th September 2003 19:53
Downloads: 907
Keywords: 


Abstract:

In constraint satisfaction problems over finite domains, some variables
can be frozen, that is, they take the same value in all possible solutions. We study the complexity of the problem of recognizing frozen variables with restricted sets of constraint relations allowed in the
instances. We show that the complexity of such problems is determined
by certain algebraic properties of these relations. We characterize all
tractable problems, and describe large classes of NP-complete, coNP-complete, and DP-complete problems. As an application of these results, we completely classify the complexity of the problem in two cases: (1) with domain size 2; and (2) when all unary relations are present. We also give a rough classification for domain size 3.



ISSN 1433-8092 | Imprint