Dalmau, VíctorKrokhin, Andrei2019-01-212019-01-212008Dalmau V, Krokhin A. Majority constraints have bounded pathwidth duality. Eur J Comb. 2008 May;29(4):821-37. DOI: 10.1016/j.ejc.2007.11.0200195-6698http://hdl.handle.net/10230/36342We 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.application/pdfeng© Elsevier http://dx.doi.org/10.1016/j.ejc.2007.11.020info:eu-repo/semantics/articlehttp://dx.doi.org/10.1016/j.ejc.2007.11.020info:eu-repo/semantics/openAccess