Show simple item record Dalmau, Víctor Krokhin, Andrei 2019-01-21T09:04:38Z 2019-01-21T09:04:38Z 2008
dc.identifier.citation Dalmau 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.020
dc.identifier.issn 0195-6698
dc.description.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.
dc.description.sponsorship This work was partially supported by the UK EPSRC grant EP/C54384X/1. Part of this work was done when both authors visited the Isaac Newton Institute for Mathematical Sciences, Cambridge. The financial support provided by the Institute is gratefully acknowledged. The first author is also supported by the MEC under the program “Ramon y Cajal”, grants TIC 2002-04470-C03, TIC 2002-04019-C03, TIN 2004-04343, the EU PASCAL Network of Excellence IST-2002-506778, and the MODNET Marie Curie Research Training Network MRTN-CT-2004-512234. The second author is also supported by the UK EPSRC grant EP/C543831/1.
dc.format.mimetype application/pdf
dc.language.iso eng
dc.publisher Elsevier
dc.relation.ispartof European Journal of Combinatorics. 2008 May;29(4):821-37.
dc.rights © Elsevier
dc.title Majority constraints have bounded pathwidth duality
dc.type info:eu-repo/semantics/article
dc.relation.projectID info:eu-repo/grantAgreement/ES/1PN/TIC2002-04470-C03
dc.relation.projectID info:eu-repo/grantAgreement/ES/1PN/TIC2002-04019-C03
dc.relation.projectID info:eu-repo/grantAgreement/ES/2PN/TIN2004-04343
dc.relation.projectID info:eu-repo/grantAgreement/EC/FP6/506778
dc.relation.projectID info:eu-repo/grantAgreement/EC/FP6/512234
dc.rights.accessRights info:eu-repo/semantics/openAccess
dc.type.version info:eu-repo/semantics/acceptedVersion

This item appears in the following Collection(s)

Show simple item record

Search DSpace

Advanced Search


My Account


Compliant to Partaking