Gaspers, Serge ;
Ordyniak, Sebastian ;
Ramanujan, M. S. ;
Saurabh, Saket ;
Szeider, Stefan
Backdoors to qHorn
Abstract
The class qHorn, introduced by Boros, Crama and Hammer in 1990, is one of the largest known classes of propositional CNF formulas for which satisfiability can be decided in polynomial time. This class properly contains the fundamental classes of Horn and Krom formulas as well as the class of renamable (or disguised) Horn formulas.
In this paper we extend this class so that its favorable algorithmic properties can be made accessible to formulas that are outside but "close"' to this class. We show that deciding satisfiability is fixedparameter tractable parameterized by the distance of the given formula from qHorn. The distance is measured by the smallest number of variables that we need to delete from the formula in order to get a qHorn formula, i.e., the size of a smallest deletion backdoor set into the class qHorn.
This result generalizes known fixedparameter tractability results for satisfiability decision with respect to the parameters distance from Horn, Krom, and renamable Horn.
BibTeX  Entry
@InProceedings{gaspers_et_al:LIPIcs:2013:3923,
author = {Serge Gaspers and Sebastian Ordyniak and M. S. Ramanujan and Saket Saurabh and Stefan Szeider},
title = {{Backdoors to qHorn}},
booktitle = {30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)},
pages = {6779},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897507},
ISSN = {18688969},
year = {2013},
volume = {20},
editor = {Natacha Portier and Thomas Wilke},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2013/3923},
URN = {urn:nbn:de:0030drops39236},
doi = {10.4230/LIPIcs.STACS.2013.67},
annote = {Keywords: Algorithms and data structures, Backdoor sets, Satisfiability, Fixed Parameter Tractability}
}
2013
Keywords: 

Algorithms and data structures, Backdoor sets, Satisfiability, Fixed Parameter Tractability 
Seminar: 

30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)

Issue date: 

2013 
Date of publication: 

2013 