The Dichotomy for Conservative Constraint Satisfaction is Polynomially Decidable
Clément Carbonnel · arXiv (Cornell University) · 2016
Given a fixed constraint language $Γ$, the conservative CSP over $Γ$ (denoted by c-CSP($Γ$)) is a variant of CSP($Γ$) where the domain of each variable can be restricted arbitrarily. A dichotomy is known for conservative CSP: for every fixed language $Γ$, c-CSP($Γ$) is either in P or NP-complete. However, the characterization of conservatively tractable languages is of algebraic nature and the naive recognition algorithm is super-exponential in the domain size. The main contribution of this paper is a polynomial-time algorithm that, given a constraint language $Γ$ as input, decides if c-CSP($Γ$) is tractable. In addition, if $Γ$ is proven tractable the algorithm also outputs its coloured graph, which contains valuable information on the structure of $Γ$.