The Dichotomy for Conservative Constraint Satisfaction is Polynomially Decidable

Given a fixed constraint language \(\varGamma \), the conservative CSP over \(\varGamma \) (denoted by c-CSP(\(\varGamma \))) is a variant of CSP(\(\varGamma \)) where the domain of each variable can be restricted arbitrarily. In [5] a dichotomy has been proven for conservative CSP: for every fixed language \(\varGamma \), c-CSP(\(\varGamma \)) is either in P or NP-complete. However, the characterization of conservatively tractable languages is of algebraic nature and the recognition algorithm provided in [5] is super-exponential in the domain size. The main contribution of this paper is a polynomial-time algorithm that, given a constraint language \(\varGamma \) as input, decides if c-CSP(\(\varGamma \)) is tractable. In addition, if \(\varGamma \) is proven tractable the algorithm also outputs its coloured graph, which contains valuable information on the structure of \(\varGamma \).