2026-08-02T17:39:56Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6962 2024-03-06T10:28:04Z ddc:004 open_access

Backdoor Sets for CSP Gaspers, Serge Ordyniak, Sebastian Szeider, Stefan Backdoor sets Constraint satisfaction problems Parameterized complexity Polymorphisms 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Serge Gaspers and Sebastian Ordyniak and Stefan Szeider 2017 Is Part Of Dagstuhl Follow-Ups, Volume 7, The Constraint Satisfaction Problem: Complexity and Approximability (2017) InCollection Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/DFU.Vol7.15301.137 urn:nbn:de:0030-drops-69626 https://drops.dagstuhl.de/entities/document/10.4230/DFU.Vol7.15301.137 eng https://creativecommons.org/licenses/by/3.0/legalcode