OATAO - Open Archive Toulouse Archive Ouverte Open Access Week

On Backdoors To Tractable Constraint Languages

Carbonnel, Clément and Cooper, Martin C. and Hébrard, Emmanuel On Backdoors To Tractable Constraint Languages. (2014) In: International Conference on Principles and Practice of Constraint Programming - CP 2014, 8 September 2014 - 12 September 2014 (Lyon, France).

[img]
Preview
(Document in English)

PDF (Author's version) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
508kB

Official URL: http://dx.doi.org/10.1007/978-3-319-10428-7_18

Abstract

In the context of CSPs, a strong backdoor is a subset of variables such that every complete assignment yields a residual instance guaranteed to have a specified property. If the property allows efficient solving, then a small strong backdoor provides a reasonable decomposition of the original instance into easy instances. An important challenge is the design of algorithms that can find quickly a small strong backdoor if one exists. We present a systematic study of the parameterized complexity of backdoor detection when the target property is a restricted type of constraint language defined by means of a family of polymorphisms. In particular, we show that under the weak assumption that the polymorphisms are idempotent, the problem is unlikely to be FPT when the parameter is either $r$ (the constraint arity) or $k$ (the size of the backdoor) unless P = NP or FPT = W[2]. When the parameter is $k+r$, however, we are able to identify large classes of languages for which the problem of finding a small backdoor is FPT.

Item Type:Conference or Workshop Item (Paper)
Additional Information:Thanks to Springer editor. The definitive version is available at http://link.springer.com/book/10.1007/978-3-319-10428-7The original PDF of the article can be found at http://link.springer.com/chapter/10.1007%2F978-3-319-10428-7_18
Audience (conference):International conference proceedings
Uncontrolled Keywords:
Institution:French research institutions > Centre National de la Recherche Scientifique - CNRS (FRANCE)
Université de Toulouse > Institut National Polytechnique de Toulouse - INPT (FRANCE)
Université de Toulouse > Institut National des Sciences Appliquées de Toulouse - INSA (FRANCE)
Université de Toulouse > Institut Supérieur de l'Aéronautique et de l'Espace - ISAE-SUPAERO (FRANCE)
Université de Toulouse > Université Toulouse III - Paul Sabatier - UPS (FRANCE)
Université de Toulouse > Université Toulouse - Jean Jaurès - UT2J (FRANCE)
Université de Toulouse > Université Toulouse 1 Capitole - UT1 (FRANCE)
Laboratory name:
Funders:
Agence Nationale de la Recherche (France)
Statistics:download
Deposited By: IRIT IRIT
Deposited On:13 Apr 2015 06:43

Repository Staff Only: item control page