Title:
|
CSP duality and trees of bounded pathwidth
|
Author:
|
Carvalho, Catarina; Dalmau, Víctor; Krokhin, Andrei
|
Abstract:
|
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. |
Abstract:
|
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. |
Subject(s):
|
-Constraint satisfaction problem -Homomorphism duality -Datalog -Polymorphisms -Bounded pathwidth |
Rights:
|
© Elsevier http://dx.doi.org/10.1016/j.tcs.2010.05.016 |
Document type:
|
Article Article - Accepted version |
Published by:
|
Elsevier
|
Share:
|
|