Skip to main content

Research Repository

Advanced Search

Recognizing frozen variables in constraint satisfaction problems

Jonsson, P.; Krokhin, A.

Recognizing frozen variables in constraint satisfaction problems Thumbnail


Authors

P. Jonsson



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. Under the assumption that NP≠coNP (and consequently PTIME≠NP), 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.

Citation

Jonsson, P., & Krokhin, A. (2004). Recognizing frozen variables in constraint satisfaction problems. Theoretical Computer Science, 329(1-3), 93-113. https://doi.org/10.1016/j.tcs.2004.08.006

Journal Article Type Article
Publication Date Dec 1, 2004
Deposit Date Mar 29, 2010
Publicly Available Date Mar 28, 2024
Journal Theoretical Computer Science
Print ISSN 0304-3975
Publisher Elsevier
Peer Reviewed Peer Reviewed
Volume 329
Issue 1-3
Pages 93-113
DOI https://doi.org/10.1016/j.tcs.2004.08.006
Keywords Constraint satisfaction, Frozen variable, Computational complexity, Polymorphism.

Files





You might also like



Downloadable Citations