  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.
