# On Backdoors To Tractable Constraint Languages

arXiv: https://arxiv.org/abs/1404.3675 · HTML: https://mlsanity.com/paper/1404.3675/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Apr 2014.

## Built on by (most cited first, 1 of 1)

- [Computational Short Cuts in Infinite Domain Constraint Satisfaction](https://mlsanity.com/paper/2211.10144/) (2022)

## Abstract (arXiv)

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.