CSP duality and trees of 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.

Authors

• Catarina Carvalho
• Víctor Dalmau
• Andrei Krokhin

Keywords

• Constraint satisfaction problem
• Homomorphism duality
• Datalog
• Polymorphisms
• Bounded pathwidth