Caterpillar duality for constraint satisfaction problems

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

Abstract

The study of constraint satisfaction problems definable in various fragments of Datalog has recently gained considerable importance. We consider constraint satisfaction problems that are definable in the smallest natural recursive fragment of Datalog - monadic linear Datalog with at most one EDB per rule. We give combinatorial and algebraic characterisations of such problems, in terms of caterpillar dualities and lattice operations, respectively. We then apply our results to study graph H-colouring problems.

Citation

Carvalho, C., Dalmau, V., & Krokhin, A. (2008, June). Caterpillar duality for constraint satisfaction problems. Presented at 23rd Annual IEEE Symposium on Logic in Computer Science (LICS) 2008, Pittsburgh, Pennsylvania

• Presentation Conference Type: Conference Paper (published)
• Conference Name: 23rd Annual IEEE Symposium on Logic in Computer Science (LICS) 2008
• Publication Date: Jun 1, 2008
• Deposit Date: Mar 29, 2010
• Publicly Available Date: Nov 8, 2010
• Pages: 307 -316
• Series Title: LICS '08 Proceedings of the 2008 23rd Annual IEEE Symposium on Logic in Computer Science
• Series ISSN: 1043-6871
• Book Title: Twenty-third Annual IEEE Symposium on Logic in Computer Science, 24-27 June 2008, Pittsburgh, PA ; proceedings.
• DOI: https://doi.org/10.1109/lics.2008.19
• Keywords: Constraint satisfaction problem, Homomorphism, Duality, Caterpillar structures, Datalog.
• Public URL: https://durham-repository.worktribe.com/output/1161739
• Additional Information: June 24-June 27, 2008