Speaker: Serge Gaspers, University of New South Wales and NICTA, Sydney, Australia
Title: Backdoors to Satisfaction
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 class where the Satisfiability problem is polynomial-time decidable. 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 talk I will 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. I will also present an outline of a recent FPT-approximation algorithm finding a backdoor to the class of formulas with bounded incidence treewidth.
The talk is based on joint work with Stefan Szeider (Vienna University of Technology), which appeared at ICALP 2012, SAT 2012, FOCS 2013, and a survey in Mike Fellows' Festschrift 2012.