Backdoors to q-Horn

D 2013

Backdoors to q-Horn

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

Basic information

Original name

Backdoors to q-Horn

Authors

ORDYNIAK, Sebastian (276 Germany, guarantor, belonging to the institution), M S RAMANUJAN (356 India), Stefan SZEIDER (40 Austria), Serge GASPERS (442 Luxembourg) and Saket SAURABH (356 India)

Edition

Germany, LIPIcs, p. 67-79, 13 pp. 2013

Publisher

Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik

Other information

Language

English

Type of outcome

Stať ve sborníku

Field of Study

10000 1. Natural Sciences

Country of publisher

Germany

Confidentiality degree

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

Publication form

printed version "print"

RIV identification code

RIV/00216224:14330/13:00072816

Organization unit

Faculty of Informatics

ISBN

978-3-939897-50-7

ISSN

DOI

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

Keywords in English

satisfiability; backdoors; parameterized complexity

Abstract

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

Links

EE2.3.30.0009, research and development project

Name: Zaměstnáním čerstvých absolventů doktorského studia k vědecké excelenci

Citovat

ORDYNIAK, Sebastian, M S RAMANUJAN, Stefan SZEIDER, Serge GASPERS and Saket SAURABH. Backdoors to q-Horn. In Natacha Portier, Thomas Wilke. LIPIcs. Germany: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2013, p. 67-79. ISBN 978-3-939897-50-7. Available from: https://dx.doi.org/10.4230/LIPIcs.STACS.2013.67.

@inproceedings{1173830,
   author = {Ordyniak, Sebastian and Ramanujan, M S and Szeider, Stefan and Gaspers, Serge and Saurabh, Saket},
   address = {Germany},
   booktitle = {LIPIcs},
   doi = {http://dx.doi.org/10.4230/LIPIcs.STACS.2013.67},
   editor = {Natacha Portier, Thomas Wilke},
   keywords = {satisfiability; backdoors; parameterized complexity},
   howpublished = {tištěná verze "print"},
   language = {eng},
   location = {Germany},
   isbn = {978-3-939897-50-7},
   pages = {67-79},
   publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik},
   title = {Backdoors to q-Horn},
   year = {2013}
}

TY  - JOUR
ID  - 1173830
AU  - Ordyniak, Sebastian - Ramanujan, M S - Szeider, Stefan - Gaspers, Serge - Saurabh, Saket
PY  - 2013
TI  - Backdoors to q-Horn
PB  - Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
CY  - Germany
SN  - 9783939897507
KW  - satisfiability
KW  - backdoors
KW  - parameterized complexity
N2  - 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).
ER  -

ORDYNIAK, Sebastian, M S RAMANUJAN, Stefan SZEIDER, Serge GASPERS and Saket SAURABH. Backdoors to q-Horn. In Natacha Portier, Thomas Wilke. \textit{LIPIcs}. Germany: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2013, p.~67-79. ISBN~978-3-939897-50-7. Available from: https://dx.doi.org/10.4230/LIPIcs.STACS.2013.67.

Detailed Information on Publication Record