Backdoors into heterogeneous classes of SAT and CSP
作者：
Highlights：
• 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.
摘要
•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.
论文关键词：Constraint satisfaction,Satisfiability,Backdoor set,Parameterized complexity
论文评审过程：Received 9 September 2015, Revised 21 October 2016, Accepted 23 October 2016, Available online 3 November 2016, Version of Record 19 December 2016.
论文官网地址：https://doi.org/10.1016/j.jcss.2016.10.007
