Skip to Main content Skip to Navigation
New interface
Conference papers

The Dichotomy for Conservative Constraint Satisfaction is Polynomially Decidable

Clément Carbonnel 1 
1 LAAS-ROC - Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes
LAAS - Laboratoire d'analyse et d'architecture des systèmes
Abstract : 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. In [5] a dichotomy has been proven 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 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 Γ 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 Γ .
Complete list of metadata

Cited literature [19 references]  Display  Hide  Download
Contributor : Clément Carbonnel Connect in order to contact the contributor
Submitted on : Friday, December 9, 2016 - 2:05:15 PM
Last modification on : Tuesday, October 25, 2022 - 11:58:11 AM
Long-term archiving on: : Thursday, March 23, 2017 - 10:19:44 AM


Files produced by the author(s)



Clément Carbonnel. The Dichotomy for Conservative Constraint Satisfaction is Polynomially Decidable. 22nd International Conference on Principles and Practice of Constraint Programming (CP'16), Sep 2016, Toulouse, France. pp.130 - 146, ⟨10.1007/978-3-319-44953-1_9⟩. ⟨hal-01413124⟩



Record views


Files downloads