License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/DFU.Vol7.15301.137
URN: urn:nbn:de:0030-drops-69626
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/6962/
Go to the corresponding DFU Volume Portal

Gaspers, Serge ; Ordyniak, Sebastian ; Szeider, Stefan

Backdoor Sets for CSP

pdf-format:
DFU-Vol7-15301-5.pdf (0.6 MB)

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.

BibTeX - Entry

@InCollection{gaspers_et_al:DFU:2017:6962,
  author =	{Serge Gaspers and Sebastian Ordyniak and Stefan Szeider},
  title =	{{Backdoor Sets for CSP}},
  booktitle =	{The Constraint Satisfaction Problem: Complexity and Approximability},
  pages =	{137--157},
  series =	{Dagstuhl Follow-Ups},
  ISBN =	{978-3-95977-003-3},
  ISSN =	{1868-8977},
  year =	{2017},
  volume =	{7},
  editor =	{Andrei Krokhin and Stanislav Zivny},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/6962},
  URN =		{urn:nbn:de:0030-drops-69626},
  doi =		{10.4230/DFU.Vol7.15301.137},
  annote =	{Keywords: Backdoor sets, Constraint satisfaction problems, Parameterized complexity, Polymorphisms}
}

Keywords: Backdoor sets, Constraint satisfaction problems, Parameterized complexity, Polymorphisms
Collection: The Constraint Satisfaction Problem: Complexity and Approximability
Issue Date: 2017
Date of publication: 21.02.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI