Backdoors to q-Horn

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F16%3A00094276" target="_blank" >RIV/00216224:14330/16:00094276 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1007/s00453-014-9958-5" target="_blank" >http://dx.doi.org/10.1007/s00453-014-9958-5</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/s00453-014-9958-5" target="_blank" >10.1007/s00453-014-9958-5</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 , 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 2-CNF 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 fixed-parameter tractable parameterized by the distance of the given formula from . The distance is measured by the smallest number of variables that we need to delete from the formula in order to get a formula, i.e., the size of a smallest deletion backdoor set into the class . This result generalizes known fixed-parameter tractability results for satisfiability decision with respect to the parameters distance from Horn, 2-CNF, and renamable Horn.

Název v anglickém jazyce

Backdoors to q-Horn

Popis výsledku anglicky

The class , 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 2-CNF 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 fixed-parameter tractable parameterized by the distance of the given formula from . The distance is measured by the smallest number of variables that we need to delete from the formula in order to get a formula, i.e., the size of a smallest deletion backdoor set into the class . This result generalizes known fixed-parameter tractability results for satisfiability decision with respect to the parameters distance from Horn, 2-CNF, and renamable Horn.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2016

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 periodika

ALGORITHMICA

ISSN

0178-4617

e-ISSN

—

Svazek periodika

74

Číslo periodika v rámci svazku

1

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

18

Strana od-do

540-557

Kód UT WoS článku

000367622200020

EID výsledku v databázi Scopus

—