Tractable conservative constraint satisfaction problems

Abstract

In a constraint satisfaction problem (CSP) the aim is to find an assignment of values to a given set of variables, subject to specified constraints. The CSP is known to be NP-complete in general. However, certain restrictions on the form of the allowed constraints can lead to problems solvable in polynomial time. Such restrictions are usually imposed by specifying a constraint language. The principal research direction aims to distinguish those constraint languages which give rise to tractable CSPs from those which do not. We achieve this goal for the important version of the CSP, in which the set of values for each individual variable can be restrited arbitrarily. Restrictions of this type can be expressed by including in a constraint language all possible unary constraints. Constraint languages containing all unary constraints will be called conservative. We completely characterise conservative constraint languages that give rise to CSP classes solvable in polynomial time. In particular, this result allows us to obtain a complete description of those (directed) graphs H for which the LIST H-COLORING problem is polynomial time solvable. The result, the solution algorithm and the proof heavily use the algebraic to CSP developed by P.Jeavons and co-authors.