Skip to main content

Research Repository

Advanced Search

Majority constraints have bounded pathwidth duality

Dalmau, V.; Krokhin, A.


V. Dalmau


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.


Dalmau, V., & Krokhin, A. (2008). Majority constraints have bounded pathwidth duality. European Journal of Combinatorics, 29(4), 821-837.

Journal Article Type Article
Publication Date May 1, 2008
Deposit Date Dec 18, 2009
Journal European Journal of Combinatorics
Print ISSN 0195-6698
Publisher Elsevier
Peer Reviewed Peer Reviewed
Volume 29
Issue 4
Pages 821-837