Backdoors to q-Horn

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

Backdoors to q-Horn

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Backdoors to q-Horn

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

BD - Teorie informace

OECD FORD obor

—

Projekt

<a href="/cs/project/EE2.3.30.0009" target="_blank" >EE2.3.30.0009: Zaměstnáním čerstvých absolventů doktorského studia k vědecké excelenci</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2013

Kód důvěrnosti údajů

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

Název statě ve sborníku

LIPIcs

ISBN

9783939897507

ISSN

1868-8969

e-ISSN

—

Počet stran výsledku

13

Strana od-do

67-79

Název nakladatele

Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik

Místo vydání

Germany

Místo konání akce

Kiel, Germany

Datum konání akce

1. 1. 2013

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—