CSP duality and trees of bounded pathwidth.

Carvalho, C.; Dalmau, V.; Krokhin, A.

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.

Citation

Carvalho, C., Dalmau, V., & Krokhin, A. (2010). CSP duality and trees of bounded pathwidth. Theoretical Computer Science, 411(34-36), 3188-3208. https://doi.org/10.1016/j.tcs.2010.05.016

• Journal Article Type: Article
• Publication Date: 2010-07
• Deposit Date: Oct 5, 2010
• Journal: Theoretical Computer Science
• Print ISSN: 0304-3975
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 411
• Issue: 34-36
• Pages: 3188-3208
• DOI: https://doi.org/10.1016/j.tcs.2010.05.016
• Keywords: Constraint satisfaction problem, Homomorphism duality, Datalog, Polymorphisms, Bounded pathwidth.
• Public URL: https://durham-repository.worktribe.com/output/1539005