2026-04-14T04:46:11Zhttps://recercat.cat/oai/request

oai:recercat.cat:10230/363292025-12-24T08:46:10Zcom_2072_6col_2072_452952

CSP duality and trees of bounded pathwidth Carvalho, Catarina Dalmau, Víctor Krokhin, Andrei Constraint satisfaction problem Homomorphism duality Datalog Polymorphisms Bounded pathwidth We study non-uniform constraint satisfaction problems definable in monadic Datalog stratified by the use of non-linearity. We show how such problems can be described in terms of homomorphism dualities involving trees of bounded pathwidth and in algebraic terms. For this, we introduce a new parameter for trees that closely approximates pathwidth and can be characterised via a hypergraph searching game. The first author is supported by FCT grant SFRH/BPD/26216/2006 and also by FCT and FEDER within the project ISFL-1-143 of the Centre for Algebra of the University of Lisbon. The second author is supported by grants TIN2006-15387-C03-03 and TIN2007-68005-C04 funded by the MCyT. The third author is supported by the UK EPSRC grants EP/G011001/1 and EP/C543831/1. 2019-01-18T11:13:08Z 2019-01-18T11:13:08Z 2010 info:eu-repo/semantics/article info:eu-repo/semantics/acceptedVersion Carvalho C, Dalmau V, Krokhin A. CSP duality and trees of bounded pathwidth. Theor Comput Sci. 2010 Jul 17;411(34-36):3188-208. DOI: 10.1016/j.tcs.2010.05.016 0304-3975 http://hdl.handle.net/10230/36329 http://dx.doi.org/10.1016/j.tcs.2010.05.016 eng Theoretical Computer Science. 2010 Jul 17;411(34-36):3188-208. info:eu-repo/grantAgreement/ES/2PN/TIN2006-15387-C03-03 info:eu-repo/grantAgreement/ES/2PN/TIN2007-68005-C04 © Elsevier http://dx.doi.org/10.1016/j.tcs.2010.05.016 info:eu-repo/semantics/openAccess application/pdf application/pdf Elsevier