Majority constraints have bounded pathwidth duality

Mostra el registre complet Registre parcial de l'ítem

• dc.contributor.author Dalmau, Víctor
• dc.contributor.author Krokhin, Andrei
• dc.date.accessioned 2019-01-21T09:04:38Z
• dc.date.available 2019-01-21T09:04:38Z
• dc.date.issued 2008
• 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.en
• 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.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.doi http://dx.doi.org/10.1016/j.ejc.2007.11.020
• dc.identifier.issn 0195-6698
• dc.identifier.uri http://hdl.handle.net/10230/36342
• dc.language.iso eng
• dc.publisher Elsevier
• dc.relation.ispartof European Journal of Combinatorics. 2008 May;29(4):821-37.
• 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 © Elsevier http://dx.doi.org/10.1016/j.ejc.2007.11.020
• dc.rights.accessRights info:eu-repo/semantics/openAccess
• dc.title Majority constraints have bounded pathwidth duality
• dc.type info:eu-repo/semantics/article
• dc.type.version info:eu-repo/semantics/acceptedVersion