ALCOMFT-TR-03-57

A. Krokhin and P. Jonsson
Recognizing frozen variables in constraint satisfaction problems
Warwick. Work package 4. October 2003.

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.

keywords: constraint satisfaction, frozen variable, computational complexity

Postscript file: ALCOMFT-TR-03-57.ps.gz (126 kb).