The Dichotomy for Conservative Constraint Satisfaction is Polynomially Decidable
This provides a practical solution for researchers and practitioners in theoretical computer science dealing with constraint satisfaction, addressing a previously inefficient super-exponential recognition process.
The paper tackles the problem of efficiently deciding whether a conservative constraint satisfaction problem (c-CSP) is tractable (in P) or NP-complete, given a fixed constraint language, by developing a polynomial-time algorithm that determines this dichotomy and outputs a coloured graph for tractable cases.
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 $Γ$.