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

Barto, Libor ; Butti, Silvia

Weisfeiler-Leman Invariant Promise Valued CSPs

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

Abstract

In a recent line of work, Butti and Dalmau have shown that a fixed-template Constraint Satisfaction Problem is solvable by a certain natural linear programming relaxation (equivalent to the basic linear programming relaxation) if and only if it is solvable on a certain distributed network, and this happens if and only if its set of Yes instances is closed under Weisfeiler-Leman equivalence. We generalize this result to the much broader framework of fixed-template Promise Valued Constraint Satisfaction Problems. Moreover, we show that two commonly used linear programming relaxations are no longer equivalent in this broader framework.

BibTeX - Entry

@InProceedings{barto_et_al:LIPIcs.CP.2022.4,
  author =	{Barto, Libor and Butti, Silvia},
  title =	{{Weisfeiler-Leman Invariant Promise Valued CSPs}},
  booktitle =	{28th International Conference on Principles and Practice of Constraint Programming (CP 2022)},
  pages =	{4:1--4: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/16633},
  URN =		{urn:nbn:de:0030-drops-166332},
  doi =		{10.4230/LIPIcs.CP.2022.4},
  annote =	{Keywords: Promise Valued Constraint Satisfaction Problem, Linear programming relaxation, Distributed algorithms, Symmetric fractional polymorphisms, Color refinement algorithm}
}

Keywords: Promise Valued Constraint Satisfaction Problem, Linear programming relaxation, Distributed algorithms, Symmetric fractional polymorphisms, Color refinement algorithm
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