Harnessing tractability in constraint satisfaction problems

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 [Toulouse]
Abstract : The Constraint Satisfaction Problem (CSP) is a fundamental NP-complete problem with many applications in artificial intelligence. This problem has enjoyed considerable scientific attention in the past decades due to its practical usefulness and the deep theoretical questions it relates to. However, there is a wide gap between practitioners, who develop solving techniques that are efficient for industrial instances but exponential in the worst case, and theorists who design sophisticated polynomial-time algorithms for restrictions of CSP defined by certain algebraic properties. In this thesis we attempt to bridge this gap by providing polynomial-time algorithms to test for membership in a selection of major tractable classes. Even if the instance does not belong to one of these classes, we investigate the possibility of decomposing efficiently a CSP instance into tractable subproblems through the lens of parameterized complexity. Finally, we propose a general framework to adapt the concept of kernelization, central to parameterized complexity but hitherto rarely used in practice, to the context of constraint reasoning. Preliminary experiments on this last contribution show promising results.
Document type :
Automatic Control Engineering. Institut National Polytechnique de Toulouse, 2016. English
Liste complète des métadonnées

Cited literature [130 references]  Display  Hide  Download

Contributor : Arlette Evrard <>
Submitted on : Monday, January 30, 2017 - 2:16:00 PM
Last modification on : Thursday, January 11, 2018 - 6:27:07 AM


  • HAL Id : tel-01444799, version 1


Clément Carbonnel. Harnessing tractability in constraint satisfaction problems. Automatic Control Engineering. Institut National Polytechnique de Toulouse, 2016. English. 〈tel-01444799〉



Record views


Files downloads