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].