DFU.Vol7.15301.137.pdf
- Filesize: 0.55 MB
- 21 pages
Document
Backdoor Sets for CSP
Authors
-
Part of:
Volume:
The Constraint Satisfaction Problem: Complexity and Approximability (DFU - Vol. 7)
Series: Dagstuhl Follow-Ups (DFU) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2017-02-21
Cite As Get BibTex
Serge Gaspers, Sebastian Ordyniak, and Stefan Szeider. Backdoor Sets for CSP. In The Constraint Satisfaction Problem: Complexity and Approximability. Dagstuhl Follow-Ups, Volume 7, pp. 137-157, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/DFU.Vol7.15301.137
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.
Subject Classification
Keywords
- Backdoor sets
- Constraint satisfaction problems
- Parameterized complexity
- Polymorphisms
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads