Notice
This item was automatically migrated from a legacy system. It's data has not been checked and might not meet the quality criteria of the present system.
Gaspers, S., Misra, N., Ordyniak, S., Szeider, S., & Živný, S. (2017). Backdoors into heterogeneous classes of SAT and CSP. Journal of Computer and System Sciences, 85, 38–56. https://doi.org/10.1016/j.jcss.2016.10.007
E192-01 - Forschungsbereich Algorithms and Complexity
-
Journal:
Journal of Computer and System Sciences
-
ISSN:
0022-0000
-
Date (published):
2017
-
Number of Pages:
19
-
Peer reviewed:
Yes
-
Keywords:
Applied Mathematics; Theoretical Computer Science; General Computer Science; Computational Theory and Mathematics; Computer Networks and Communications
-
Abstract:
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.
