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).
|
(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.
Repository Staff Only: item control page