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.2022.20
URN: urn:nbn:de:0030-drops-166490
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16649/
Go to the corresponding LIPIcs Volume Portal

Dreier, Jan ; Ordyniak, Sebastian ; Szeider, Stefan

CSP Beyond Tractable Constraint Languages

pdf-format:
LIPIcs-CP-2022-20.pdf (0.8 MB)

Abstract

The constraint satisfaction problem (CSP) is among the most studied computational problems. While NP-hard, many tractable subproblems have been identified (Bulatov 2017, Zuk 2017). Backdoors, introduced by Williams, Gomes, and Selman (2003), gradually extend such a tractable class to all CSP instances of bounded distance to the class. Backdoor size provides a natural but rather crude distance measure between a CSP instance and a tractable class. Backdoor depth, introduced by Mählmann, Siebertz, and Vigny (2021) for SAT, is a more refined distance measure, which admits the parallel utilization of different backdoor variables. Bounded backdoor size implies bounded backdoor depth, but there are instances of constant backdoor depth and arbitrarily large backdoor size. Dreier, Ordyniak, and Szeider (2022) provided fixed-parameter algorithms for finding backdoors of small depth into the classes of Horn and Krom formulas.
In this paper, we consider backdoor depth for CSP. We consider backdoors w.r.t. tractable subproblems C_Γ of the CSP defined by a constraint language Γ, i.e., where all the constraints use relations from the language Γ. Building upon Dreier et al.’s game-theoretic approach and their notion of separator obstructions, we show that for any finite, tractable, semi-conservative constraint language Γ, the CSP is fixed-parameter tractable parameterized by the backdoor depth into C_Γ plus the domain size.
With backdoors of low depth, we reach classes of instances that require backdoors of arbitrary large size. Hence, our results strictly generalize several known results for CSP that are based on backdoor size.

BibTeX - Entry

@InProceedings{dreier_et_al:LIPIcs.CP.2022.20,
  author =	{Dreier, Jan and Ordyniak, Sebastian and Szeider, Stefan},
  title =	{{CSP Beyond Tractable Constraint Languages}},
  booktitle =	{28th International Conference on Principles and Practice of Constraint Programming (CP 2022)},
  pages =	{20:1--20:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-240-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{235},
  editor =	{Solnon, Christine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/16649},
  URN =		{urn:nbn:de:0030-drops-166490},
  doi =		{10.4230/LIPIcs.CP.2022.20},
  annote =	{Keywords: CSP, backdoor depth, constraint language, tractable class, recursive backdoor}
}

Keywords: CSP, backdoor depth, constraint language, tractable class, recursive backdoor
Collection: 28th International Conference on Principles and Practice of Constraint Programming (CP 2022)
Issue Date: 2022
Date of publication: 23.07.2022

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