Weisfeiler-Leman Invariant Promise Valued CSPs

Autor:	Barto, Libor, Butti, Silvia
Rok vydání:	2022
Předmět:	Computer Science - Data Structures and Algorithms Computer Science - Discrete Mathematics
Druh dokumentu:	Working Paper
Popis:	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. Comment: In Proceedings of the 28th International Conference on Principles and Practice of Constraint Programming (CP2022)
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2205.04805 Zobrazit plný text záznamu View this record from Arxiv