Skip to main content

Research Repository

Advanced Search

Dualities for constraint satisfaction problems

Bulatov, A.; Krokhin, A.; Larose, B.

Authors

A. Bulatov

B. Larose



Contributors

N. Creignou
Editor

Ph.G. Kolaitis
Editor

H. Vollmer
Editor

Abstract

In a nutshell, a duality for a constraint satisfaction problem equates the existence of one homomorphism to the non-existence of other homomorphisms. In this survey paper, we give an overview of logical, combinatorial, and algebraic aspects of the following forms of duality for constraint satisfaction problems: finite duality, bounded pathwidth duality, and bounded treewidth duality.

Citation

Bulatov, A., Krokhin, A., & Larose, B. (2008). Dualities for constraint satisfaction problems. In N. Creignou, P. Kolaitis, & H. Vollmer (Eds.), Complexity of constraints : an overview of current research themes (93-124). Springer Verlag. https://doi.org/10.1007/978-3-540-92800-3_5

Publication Date Jan 1, 2008
Deposit Date Dec 15, 2009
Publisher Springer Verlag
Pages 93-124
Series Title Lecture notes in computer science
Book Title Complexity of constraints : an overview of current research themes.
DOI https://doi.org/10.1007/978-3-540-92800-3_5