License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CP.2021.32
URN: urn:nbn:de:0030-drops-153238
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/15323/
Go to the corresponding LIPIcs Volume Portal

Jonsson, Peter ; Lagerkvist, Victor ; Ordyniak, Sebastian

Reasoning Short Cuts in Infinite Domain Constraint Satisfaction: Algorithms and Lower Bounds for Backdoors

pdf-format:
LIPIcs-CP-2021-32.pdf (0.7 MB)

Abstract

A backdoor in a finite-domain CSP instance is a set of variables where each possible instantiation moves the instance into a polynomial-time solvable class. Backdoors have found many applications in artificial intelligence and elsewhere, and the algorithmic problem of finding such backdoors has consequently been intensively studied. Sioutis and Janhunen (KI, 2019) have proposed a generalised backdoor concept suitable for infinite-domain CSP instances over binary constraints. We generalise their concept into a large class of CSPs that allow for higher-arity constraints. We show that this kind of infinite-domain backdoors have many of the positive computational properties that finite-domain backdoors have: the associated computational problems are fixed-parameter tractable whenever the underlying constraint language is finite. On the other hand, we show that infinite languages make the problems considerably harder.

BibTeX - Entry

@InProceedings{jonsson_et_al:LIPIcs.CP.2021.32,
  author =	{Jonsson, Peter and Lagerkvist, Victor and Ordyniak, Sebastian},
  title =	{{Reasoning Short Cuts in Infinite Domain Constraint Satisfaction: Algorithms and Lower Bounds for Backdoors}},
  booktitle =	{27th International Conference on Principles and Practice of Constraint Programming (CP 2021)},
  pages =	{32:1--32:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-211-2},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{210},
  editor =	{Michel, Laurent D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/15323},
  URN =		{urn:nbn:de:0030-drops-153238},
  doi =		{10.4230/LIPIcs.CP.2021.32},
  annote =	{Keywords: Constraint Satisfaction Problems, Parameterised Complexity, Backdoors}
}

Keywords: Constraint Satisfaction Problems, Parameterised Complexity, Backdoors
Collection: 27th International Conference on Principles and Practice of Constraint Programming (CP 2021)
Issue Date: 2021
Date of publication: 15.10.2021

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