[Back]


Contributions to Books:

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.



English abstract:
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.

Keywords:
Backdoor sets, Constraint satisfaction problems, Parameterized complexity, Polymorphisms

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