2026-07-22T12:14:11Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16633 2024-03-06T10:57:55Z ddc:004 open_access

Weisfeiler-Leman Invariant Promise Valued CSPs Barto, Libor Butti, Silvia Promise Valued Constraint Satisfaction Problem Linear programming relaxation Distributed algorithms Symmetric fractional polymorphisms Color refinement algorithm 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Libor Barto and Silvia Butti 2022 Is Part Of LIPIcs, Volume 235, 28th International Conference on Principles and Practice of Constraint Programming (CP 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CP.2022.4 urn:nbn:de:0030-drops-166332 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2022.4 eng https://creativecommons.org/licenses/by/4.0/legalcode