OATAO - Open Archive Toulouse Archive Ouverte Open Access Week

Harnessing tractability in constraint satisfaction problems

Carbonnel, Clément. Harnessing tractability in constraint satisfaction problems. PhD, Intelligence Artificielle, Institut National Polytechnique de Toulouse, 2016

(Document in English)

PDF - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader


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.

Item Type:PhD Thesis
Uncontrolled Keywords:
Institution:Université de Toulouse > Institut National Polytechnique de Toulouse - Toulouse INP (FRANCE)
Laboratory name:
Research Director:
Cooper, Martin and Hébrard, Emmanuel
Deposited On:22 May 2017 07:25

Repository Staff Only: item control page