论文标题
WEISFEILER-LEMAN不变的承诺有价值的CSP
Weisfeiler-Leman Invariant Promise Valued CSPs
论文作者
论文摘要
在最近的工作中，BUTTI和DALMAU表明，固定的模板约束满意度问题可以通过某种自然线性编程放松（等效于基本线性编程放松）可以解决，并且仅当它在某个分布式网络上可求解时，并且仅当它在Weelfefeiler-Leman Equilentens Insecles of ysemances时才发生时才发生。我们将此结果概括为固定模板有望有价值的约束满意度问题的更广泛的框架。此外，我们表明，在这个更广泛的框架中，两种常用的线性编程放松不再等效。
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.
