You are viewing a javascript disabled version of the site. Please enable Javascript for this site to function properly.
Go to headerGo to navigationGo to searchGo to contentsGo to footer
In content section. Select this link to jump to navigation

Matched Formulas and Backdoor Sets1


We demonstrate hardness results for the detection of small backdoor sets with respect to base classes Mr of CNF formulas with maximum deficiency r (M0 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.