The collapse of the bounded width hierarchy
Libor Barto · Journal of Logic and Computation · 2014
We show that every constraint satisfaction problem (CSP) over a fixed constraint language that has bounded relational width has also relational width (2,3). Together with known results this gives a trichotomy: a CSP has either relational width 1, or relational width (2,3) (and no smaller relational width), or does not have bounded relational width. A consequence of this result is that if Γ is a finite constraint language containing relations of arity at most k , then the CSP over Γ either cannot be solved by a Datalog program, or can be solved by a Datalog program consisting of rules with at most max{3,k} variables and at most 2 variables in the head.