2016/04/24 by Clément Carbonnel, Carbonnel, Clément
Computer Science · #Constraint Satisfaction and Optimization #Advanced Graph Theory Research #semigroups and automata theory
paper · doi:10.48550/arxiv.1604.07063
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 Γ.