CSP duality and trees of bounded pathwidth

Catarina Carvalho, Víctor Dalmau, Andrei Krokhin

Research output: Contribution to journalArticlepeer-review

6 Citations (Scopus)


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.
Original languageEnglish
Pages (from-to)3188-3208
JournalTheoretical Computer Science
Issue number34-36
Publication statusPublished - 2010


Dive into the research topics of 'CSP duality and trees of bounded pathwidth'. Together they form a unique fingerprint.

Cite this