Dualities for constraint satisfaction problems

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

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
• Public URL: https://durham-repository.worktribe.com/output/1661748