Backdoors into heterogeneous classes of SAT and CSP

- Introduction of Heterogeneous Base classes for SAT and CSP.
- Introduction of base classes for CSP defined via polymorphisms.
- Complete parameterized complexity classification for strong and weak backdoor set detection for SAT and CSP.
- The paper is a largely extended version of the paper with the same title, which appeared in the Proceedings of the 28th AAAI Conference on Artificial Intelligence (AAAI'14). In addition to containing the full proofs and more detailed explanations, the paper has been extended by the following results:
- a complete parameterized complexity classification for strong backdoor set detection for SAT of heterogeneous base classes resulting from combinations of the well-known Schaefer classes,
- we now handle not only strong but also weak backdoor sets,
- the running times of all strong backdoor set detection algorithms for SAT have been improved from double to single exponential (parameter dependence),
- a comparision to related work has been added to the introduction,
- a complete comparision to partition backdoor sets has been added as an extra section.

In this paper we extend the classical notion of strong and weak backdoor sets for SAT and CSP by allowing that different instantiations of the backdoor variables result in instances that belong to different base classes; the union of the base classes forms a heterogeneous base class. Backdoor sets to heterogeneous base classes can be much smaller than backdoor sets to homogeneous ones, hence they are much more desirable but possibly harder to find. We draw a detailed complexity landscape for the problem of detecting strong and weak backdoor sets into heterogeneous base classes for SAT and CSP.