[Zurück]

S. Gaspers, St. Szeider:
"Backdoors to Satisfaction";
in: "The Multivariate Algorithmic Revolution and Beyond Essays Dedicated to Michael R. Fellows on the Occasion of His 60th Birthday", H.L. Bodlaender, R. Downey, F. Fomin, D. Marx (Hrg.); Springer LNCS, Berlin / Heidelberg, 2012, ISBN: 978-3-642-30890-1, S. 287 - 317.

A backdoor set is a set of variables of a propositional formula such that fixing the truth values of the variables in the backdoor set moves the formula into some polynomial-time decidable class. If we know a small backdoor set we can reduce the question of whether the given formula is satisfiable to the same question for one or several easy formulas that belong to the tractable class under consideration. In this survey we review parameterized complexity results for problems that arise in the context of backdoor sets, such as the problem of finding a backdoor set of size at most k , parameterized by k . We also discuss recent results on backdoor sets for problems that are beyond NP.

http://dx.doi.org/10.1007/978-3-642-30891-8_15

Projektleitung Stefan Szeider:
The Parameterized Complexity of Reasoning Problems