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

**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 Symposium on Logic in Computer Science (LICS 2004)}, year = {2004}, month = {July}, pages = {448--457}, location = {Turku, Finland}, publisher = {IEEE Computer Society Press} }