D 2013

Backdoors to q-Horn

ORDYNIAK, Sebastian, M S RAMANUJAN, Stefan SZEIDER, Serge GASPERS, Saket SAURABH et. al.

Základní údaje

Originální název

Backdoors to q-Horn

Autoři

ORDYNIAK, Sebastian (276 Německo, garant, domácí), M S RAMANUJAN (356 Indie), Stefan SZEIDER (40 Rakousko), Serge GASPERS (442 Lucembursko) a Saket SAURABH (356 Indie)

Vydání

Germany, LIPIcs, od s. 67-79, 13 s. 2013

Nakladatel

Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10000 1. Natural Sciences

Stát vydavatele

Německo

Utajení

není předmětem státního či obchodního tajemství

Forma vydání

tištěná verze "print"

Kód RIV

RIV/00216224:14330/13:00072816

Organizační jednotka

Fakulta informatiky

ISBN

978-3-939897-50-7

ISSN

DOI

http://dx.doi.org/10.4230/LIPIcs.STACS.2013.67

Klíčová slova anglicky

satisfiability; backdoors; parameterized complexity

Štítky

core_B, firank_A

Příznaky

Mezinárodní význam, Recenzováno
Změněno: 24. 4. 2014 19:23, RNDr. Pavel Šmerk, Ph.D.

Anotace

V originále

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 that satisfiability 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. This result generalizes known fixed-parameter tractability results for satisfiability decision with respect to the parameters distance from Horn or 2CNF (Nishimura, Ragde, Szeider 2004), and with respect to renamable Horn (Razgon, O'Sullivan 2009).

Návaznosti

EE2.3.30.0009, projekt VaV
Název: Zaměstnáním čerstvých absolventů doktorského studia k vědecké excelenci
Zobrazeno: 14. 11. 2024 00:45