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

Article type: Research Article

Authors: Szeider, Stefan

Affiliations: Department of Computer Science, Durham University, Durham DH1 3LE, England, United Kingdom. E-mail: [email protected]

Note: [1] A preliminary and shortened version appeared in the Proceedings of SAT 2007.

Keywords: maximum deficiency, backdoor sets, parameterized complexity

DOI: 10.3233/SAT190059

Journal: Journal on Satisfiability, Boolean Modeling and Computation, vol. 6, no. 1-3, pp. 1-12, 2010

Received 1 December 2007
|
Revision received 1 June 2008
|
Published: 1 September 2008
Get PDF open access

Abstract

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.

Show more