Informatické kolokvium 6. 3. Backdoors to Tractability for Constraint Satisfaction
Informatické kolokvium 6. 3. 2018, 14:00 posluchárna D2
RNDr. Robert Ganian, Ph.D., Algorithms and Complexity Group, TU Wien
Backdoors to Tractability for Constraint Satisfaction
Abstrakt: Constraint Satisfaction (CSP) is one of the most studied NP-complete
problems, with numerous applications in both theory and practice and featuring
its own dedicated conference. A significant amount of research has targeted the
identification of classes of CSP instances which are polynomially tractable;
this has led to celebrated results such as Schaefer's Dichotomy Theorem and
Bulatov's recent proof of the Feder-Vardi Dichotomy Conjecture. Such classes of
instances are often called "islands of tractability".
In this talk, we will present techniques and recent developments on solving CSP
instances that lie outside of an island of tractability. In particular, we will
use the notion of "backdoors" to capture the distance of an instance from an
island of tractability and show how these backdoors can be exploited to obtain
algorithms for CSP with good runtime guarantees.