On Backdoors To Tractable Constraint Languages
This addresses a key challenge in CSP solving for researchers and practitioners by providing theoretical insights into when backdoor detection can be efficient, though it is incremental as it builds on existing parameterized complexity frameworks.
The paper tackles the problem of efficiently finding small strong backdoors in constraint satisfaction problems (CSPs) to decompose instances into tractable subproblems, showing that detection is unlikely to be fixed-parameter tractable (FPT) for parameters like backdoor size or constraint arity under standard complexity assumptions, but becomes FPT when combining these parameters for many constraint languages.
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.