Backdoors to Acyclic SAT
Proceedings of ICALP 2012 (Track A: Algorithms, Complexity and Games), the 39th International Colloquium on Automata, Languages and Programming, 9-13 July 2012, University of Warwick, UK. Lecture Notes in Computer Science, vol. 7391, pp. 363-374, Springer-Verlag, 2012.
Abstract:Backdoor sets contain certain key variables of a CNF formula F that make it easy to solve the formula. More specifically, a weak backdoor set of F is a set X of variables such that there exits a truth assignment t to X that reduces F to a satisfiable formula F[t] that belongs to a polynomial-time decidable base class C. A strong backdoor set is a set X of variables such that for all assignments t to X, the reduced formula F[t] belongs to C.
We study the problem of finding backdoor sets of size at most k with respect to the base class of CNF formulas with acyclic incidence graphs, taking k as the parameter. We show that
Preprint available from Arxiv.org: 1110.6384.