Sherali-Adams层次结构和Weisfeiler-Leman层次结构在（基于承诺价值的）约束满足问题中的应用

《ACM Transactions on Computation Theory》：The Sherali-Adams and Weisfeiler-Leman Hierarchies in (Promise Valued) Constraint Satisfaction Problems

分数松弛下关系结构同态与同构的线性规划刻画及CSP类闭包条件研究。通过组合刻画线性规划放松与Weisfeiler-Leman不变性，证明满足该不变性的CSP封闭类恰好可解于分数松弛。扩展Sherali-Adams层次到同态IP，推广Weisfeiler-Leman逻辑测试到关系结构。

　　

摘要

在本文中，我们研究了整数程序（IPs）的所谓“分数松弛”之间的相互作用，这些整数程序用于编码关系结构之间的同态和同构。我们给出了同态的某种自然线性规划（LP）松弛形式的组合学表征，该表征基于分数同构的概念。研究结果表明，能够通过这种线性规划解决的约束满足问题（CSPs）家族，正是那些满足我们称之为“Weisfeiler-Leman不变性”的等价关系的问题。此外，我们将这一结果推广到了更广泛的“Promise Valued Constraint Satisfaction Problems”框架中，该框架结合了CSP框架的两个著名扩展。最后，我们考虑了通过分别应用Sherali-Adams方法和Weisfeiler-Leman方法得到的同态和同构整数程序的逐步严格化的层次结构。我们将对基本LP的组合学表征扩展到了Sherali-Adams层次结构的更高层次，并将图论中著名的Weisfeiler-Leman测试的逻辑表征推广到了关系结构上。