Matched Formulas and Backdoor SetsJournal on Satisfiability, Boolean Modeling and Computation, vol. 6, pp. 1-12, 2009. A preliminary and shortened version appeared in the Proceedings of SAT 2007, Lecture Notes in Computer Science, vol. 4501, pp. 94-99, 2007. Abstract:We demonstrate hardness results for the detection of small backdoor sets with respect to base classes Mr of CNF formulas with maximum deficiency at most r (Mr 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 Mr-backdoor set.Download: [paper pdf] |