Logic in Computer Science (LICS 2004)

Paper: A Graph of a Relational Structure and Constraint Satisfaction Problems (at LICS 2004)

Authors: Andrei A. Bulatov

Abstract

In the constraint satisfaction problem CSP(H) corresponding to a finite relational structure H, the aim is to decide, given a relational structure G, whether there exists a homomorphism from G to H. In [Tractable conservative constraint satisfaction problems], we proved that if H is a conservative structure, then it can be associated with a complete edge-3-colored graph whose vertex set is the universe of H. The complexity and a solution algorithm for CSP(H) strongly depend on certain properties of the associated graph. In this paper we show how a similar edge-3-colored graph can be defined for an arbitrary finite relational structure H. Then we study properties of the defined graph and find a solution algorithm for CSP(H), where G(H) satisfies some restrictions. The latter result substantially generalizes the results of [1, 8, 12, 25, 27] concerning max-closed constraints and constraints with a 2-semilattice, semigroup or conservative groupoid polymorphism. Finally, we complete the study of the complexity of maximal constraint languages started in [The complexity of maximal constraint languages].

BibTeX

  @InProceedings{Bulatov-AGraphofaRelational,
    author = 	 {Andrei A. Bulatov},
    title = 	 {A Graph of a Relational Structure and Constraint Satisfaction Problems},
    booktitle =  {Proceedings of the Nineteenth Annual IEEE Symp. on Logic in Computer Science, {LICS} 2004},
    year =	 2004,
    editor =	 {Harald Ganzinger},
    month =	 {July}, 
    pages =      {448--457},
    location =   {Turku, Finland}, 
    publisher =	 {IEEE Computer Society Press}
  }