S. Szeider, S. Ordyniak, S. Gaspers:

"The Constraint Satisfaction Problem: Complexity and Approximability";

in: "The Constraint Satisfaction Problem: Complexity and Approximability", Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany, Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2017, ISBN: 978-3-95977-003-3, 137 - 157.

A backdoor set of a CSP instance is a set of variables whose

instantiation moves the instance into a fixed class of tractable

instances (an island of tractability). An interesting algorithmic task

is to find a small backdoor set efficiently: once it is found we can

solve the instance by solving a number of tractable

instances. Parameterized complexity provides an adequate framework for

studying and solving this algorithmic task, where the size of the

backdoor set provides a natural parameter. In this survey we present

some recent parameterized complexity results on CSP backdoor sets,

focusing on backdoor sets into islands of tractability that are

defined in terms of constraint languages.

Backdoor sets, Constraint satisfaction problems, Parameterized complexity, Polymorphisms

Created from the Publication Database of the Vienna University of Technology.