Résumé
Given a fixed constraint language Gamma, the conservative CSP over G (denoted by c-CSP(Gamma)) is a variant of CSP(Gamma) where the domain of each variable can be restricted arbitrarily. In [5] a dichotomy has been proven for conservative CSP: for every fixed language Gamma, c-CSP(Gamma) 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 Gamma as input, decides if c-CSP(Gamma) is tractable. In addition, if Gamma is proven tractable the algorithm also outputs its coloured graph, which contains valuable information on the structure of Gamma.