CSP FOR BINARY CONSERVATIVE RELATIONAL STRUCTURES
Alexandr Kazda · 2016
We prove that whenever $${\mathbb {A}}$$ is a 3-conservative relational structure with only binary and unary relations, then the algebra of polymorphisms of $${\mathbb {A}}$$ either has no Taylor operation (i.e., CSP( $${\mathbb {A}}$$ ) is NP-complete), or it generates an SD( $${\wedge}$$ ) variety (i.e., CSP( $${\mathbb {A}}$$ ) has bounded width).