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 metadatas

Cited literature [19 references]  Display  Hide  Download

https://hal.archives-ouvertes.fr/hal-01413124
Contributor : Clément Carbonnel <>
Submitted on : Friday, December 9, 2016 - 2:05:15 PM
Last modification on : Friday, January 10, 2020 - 9:10:16 PM
Long-term archiving on: Thursday, March 23, 2017 - 10:19:44 AM

File

dicho.pdf
Files produced by the author(s)

Identifiers

Citation

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⟩

Share

Metrics

Record views

179

Files downloads

168