Backdoors to q-Horn

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F13%3A00072816" target="_blank" >RIV/00216224:14330/13:00072816 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.4230/LIPIcs.STACS.2013.67" target="_blank" >http://dx.doi.org/10.4230/LIPIcs.STACS.2013.67</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.4230/LIPIcs.STACS.2013.67" target="_blank" >10.4230/LIPIcs.STACS.2013.67</a>

Result language
angličtina
Original language name
Backdoors to q-Horn
Original language description
The class q-Horn, introduced by Boros, Crama and Hammer in 1990, is one of the largest known classes of propositional CNF fomulas for which satisfiability decision is polynomial. This class properly contains the fundamental classes of Horn and 2CNF formulas as well as the class of renamable (or disguised) Horn formulas. In this paper we gradually extend this class such that its favorable algorithmic properties can be made accessible to formulas that are outside but ``close'' to this class. We show thatsatisfiability decision is fixed-parameter tractable parameterized by the distance of the given formula from q-Horn. The distance is measured as the smallest number of variables that we need to delete from F in order to get a q-Horn formula, i.e., the size of a smallest deletion backdoor set into the class q-Horn.
Czech name
—
Czech description
—

Project
<a href="/en/project/EE2.3.30.0009" target="_blank" >EE2.3.30.0009: Employment of Newly Graduated Doctors of Science for Scientific Excellence</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year
2013
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)