Matched Formulas and Backdoor Sets 1

Abstract

We demonstrate hardness results for the detection of small backdoor sets with respect to base classes ${\mathcal{M}}_{\mathit{r}}$ of CNF formulas with maximum deficiency $⩽\mathit{r}$ ( ${\mathcal{M}}_0$ is the class of matched formulas). One of the results applies also to a wide range of base classes with added ‘empty clause detection’ as recently considered by Dilkina, Gomes, and Sabharwal. We obtain the hardness results in the framework of parameterized complexity, considering the upper bound on the size of smallest backdoor sets as the parameter. Furthermore we compare the generality of the parameters maximum deficiency and the size of a smallest ${\mathcal{M}}_{\mathit{r}}$ -backdoor set.