News and events archive

Informatics colloquium 6. 3. 2018, 14:00 lecture hall D2 RNDr. Robert Ganian, Ph.D., Algorithms and Complexity Group, TU Wien Backdoors to Tractability for Constraint Satisfaction Abstract: 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.