CSP for binary conservative relational structures
arXiv:1112.1099 · doi:10.1007/s00012-015-0358-8
Abstract
We prove that whenever A is a 3-conservative relational structure with only binary and unary relations then the algebra of polymorphisms of A either has no Taylor operation (i.e. CSP(A) is NP-complete), or generates a congruence meet semidistributive variety (i.e. CSP(A) has bounded width).
9 pages, 3 figures