Bounded width problems and algebras
by
Laszlo Zadori
Bolyai Institute, Szeged, Hungary
Coauthors: Benoit Larose

We investigate the class of bounded width CSPs (constraint satisfaction problems) for relational structures. This special class of polynomial- time CSPs was introduced by Feder and Vardi in a 1999 paper.In our study of bounded width CSPs we assign an algebra to every relational structure. We show that if the CSP for the structure has bounded width then the variety generated by the algebra omits the Hobby-McKenzie types 1 and 2. We conjecture that the converse of this statement also holds.

In their paper Feder and Vardi proved that the CSP for any structure is polynomial-time equivalent to the retraction problem for a poset obtained by a certain procedure from the structure. We call this poset the Feder-Vardi poset of the structure. We show that if the retraction problem for the Feder-Vardi poset has bounded width then the CSP for the structure also has bounded width. We do not know if the converse of this claim is true.

Date received: May 1, 2004