Paper: Caterpillar Duality for Constraint Satisfaction Problems (at LICS 2008)

Authors: Catarina Carvalho Víctor Dalmau Andrei A. Krokhin

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.

BibTeX

  @InProceedings{CarvalhoDalmauKrokh-CaterpillarDualityf,
    author = 	 {Catarina Carvalho and Víctor Dalmau and Andrei A. Krokhin},
    title = 	 {Caterpillar Duality for Constraint Satisfaction Problems},
    booktitle =  {Proceedings of the Twenty-Third Annual IEEE Symposium on Logic in Computer Science (LICS 2008)},
    year =	 {2008},
    month =	 {June}, 
    pages =      {307--316},
    location =   {Pittsburgh, PA, USA}, 
    publisher =	 {IEEE Computer Society Press}
  }