Journal on Satisfiability, Boolean Modeling and Computation ISSN:
JSAT is an open access peer reviewed journal, publishing high quality original research papers and
survey papers which evidently contribute to deeper insight. It is an electronic medium, guaranteeing
JSAT volume 12
JSAT promotes Open Science. As such, the authors are encouraged to provide additional resources to complement their article:
The above icons before the title of the article mean that the article is complemented by those resources. Articles provided all of them are awarded the open science badge.
Table of Contents
Backdoors into Two Occurrences, Jan Johannsen, 1-15.
Backdoor set fixed-parameter tractability parameterized complexity completeness formulas with two variable occurrences
Abstract: Backdoor sets for the class CNF(2) of CNF-formulas in which every variable has at most two occurrences are studied in terms of parameterized complexity. The question whether there exists a CNF(2)-backdoor set of size k is hard for the class W , for both weak and strong backdoors, and in both cases it becomes fixed-parameter tractable when restricted to inputs in d-CNF for a fixed d . Besides that, it is shown that the problem of finding weak backdoor sets is W-complete, for certain tractable cases. These are the first completeness results in lower levels of the W-hierarchy for any backdoor set problems.