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

Carbonnel, Clément

On Redundancy in Constraint Satisfaction Problems

pdf-format:
LIPIcs-CP-2022-11.pdf (0.7 MB)

Abstract

A constraint language Γ has non-redundancy f(n) if every instance of CSP(Γ) with n variables contains at most f(n) non-redundant constraints. If Γ has maximum arity r then it has non-redundancy O(n^r), but there are notable examples for which this upper bound is far from the best possible. In general, the non-redundancy of constraint languages is poorly understood and little is known beyond the trivial bounds Ω(n) and O(n^r).
In this paper, we introduce an elementary algebraic framework dedicated to the analysis of the non-redundancy of constraint languages. This framework relates redundancy-preserving reductions between constraint languages to closure operators known as pattern partial polymorphisms, which can be interpreted as generic mechanisms to generate redundant constraints in CSP instances. We illustrate the power of this framework by deriving a simple characterisation of all languages of arity r having non-redundancy Θ(n^r).

BibTeX - Entry

@InProceedings{carbonnel:LIPIcs.CP.2022.11,
  author =	{Carbonnel, Cl\'{e}ment},
  title =	{{On Redundancy in Constraint Satisfaction Problems}},
  booktitle =	{28th International Conference on Principles and Practice of Constraint Programming (CP 2022)},
  pages =	{11:1--11:15},
  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/16640},
  URN =		{urn:nbn:de:0030-drops-166409},
  doi =		{10.4230/LIPIcs.CP.2022.11},
  annote =	{Keywords: Constraint satisfaction problem, redundancy, universal algebra, extremal combinatorics}
}

Keywords: Constraint satisfaction problem, redundancy, universal algebra, extremal combinatorics
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