Upper and Lower Bounds for Weak Backdoor Set Detection

Logo poskytovatele

Varování

Publikace nespadá pod Pedagogickou fakultu, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.
Autoři

NEELDHARA Misra ORDYNIAK Sebastian RAMAN Venkatesh SZEIDER Stefan

Rok publikování 2013
Druh Článek ve sborníku
Konference Lecture Notes in Computer Science
Fakulta / Pracoviště MU

Fakulta informatiky

Citace
Doi http://dx.doi.org/10.1007/978-3-642-39071-5_29
Obor Teorie informace
Klíčová slova satisfiability; weak backdoor sets;parameterized complexity; upper bounds; lower bounds
Popis We obtain upper and lower bounds for running times of exponential time algorithms for the detection of weak backdoor sets of 3CNF formulas, considering various base classes. These results include (omitting polynomial factors), (i)~a 4.54^k algorithm to detect whether there is a weak backdoor set of at most k variables into the class of Horn formulas; (ii)~a 2.27^k algorithm to detect whether there is a weak backdoor set of at most k variables into the class of Krom formulas. These bounds improve an earlier known bound of 6^k. We also prove a 2^k lower bound for these problems, subject to the Strong Exponential Time Hypothesis.
Související projekty:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.