The Dichotomy for Conservative Constraint Satisfaction is Polynomially Decidable

Clément Carbonnel

Given a fixed constraint language $\Gamma$, the conservative CSP over $\Gamma$ (denoted by c-CSP($\Gamma$)) is a variant of CSP($\Gamma$) where the domain of each variable can be restricted arbitraril…