Paper: A Characterisation of First-Order Constraint Satisfaction Problems (at LICS 2006)

Authors: Benoit Larose Cynthia Loten Claude Tardif

Abstract

We characterise finite relational core structures admitting finitely many obstructions, in terms of special nearunanimity functions, and in terms of dismantling properties of their square. As a consequence, we show that it is decidable to determine whether a constraint satisfaction problem is first-order definable: we show the general problem to be NP-complete, and give a polynomial-time algorithm in the case of cores.

BibTeX

  @InProceedings{LaroseLotenTardif-ACharacterisationof,
    author = 	 {Benoit Larose and Cynthia Loten and Claude Tardif},
    title = 	 {A Characterisation of First-Order Constraint Satisfaction Problems},
    booktitle =  {Proceedings of the Twenty-First Annual IEEE Symposium on Logic in Computer Science (LICS 2006)},
    year =	 {2006},
    month =	 {August}, 
    pages =      {201--210},
    location =   {Seattle, Washington, USA}, 
    publisher =	 {IEEE Computer Society Press}
  }