Majority constraints have bounded pathwidth duality

Dalmau, V.; Krokhin, A.

Abstract

We study certain constraint satisfaction problems which are the problems of deciding whether there exists a homomorphism from a given relational structure to a fixed structure with a majority polymorphism. We show that such a problem is equivalent to deciding whether the given structure admits a homomorphism from an obstruction belonging to a certain class of structures of bounded pathwidth. This implies that the constraint satisfaction problem for any fixed structure with a majority polymorphism is in NL.

Citation

Dalmau, V., & Krokhin, A. (2008). Majority constraints have bounded pathwidth duality. European Journal of Combinatorics, 29(4), 821-837. https://doi.org/10.1016/j.ejc.2007.11.020

• Journal Article Type: Article
• Publication Date: May 1, 2008
• Deposit Date: Dec 18, 2009
• Journal: European Journal of Combinatorics
• Print ISSN: 0195-6698
• Electronic ISSN: 1095-9971
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 29
• Issue: 4
• Pages: 821-837
• DOI: https://doi.org/10.1016/j.ejc.2007.11.020
• Public URL: https://durham-repository.worktribe.com/output/1554984