The Sherali–Adams and Weisfeiler–Leman Hierarchies in (Promise Valued) Constraint Satisfaction Problems
Open Access
- 25 February 2026
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Computation Theory
- Vol. 18 (1) , 1-37
Abstract
In this article, we study the interactions between so-called fractional relaxations of the integer programs (IPs) which encode homomorphism and isomorphism of relational structures. We give a combinatorial characterization of a certain natural linear programming (LP) relaxation of homomorphism in terms of fractional isomorphism. As a result, we show that the families of constraint satisfaction problems (CSPs) that are solvable by such linear program are precisely those that are closed under an equivalence relation which we call Weisfeiler-Leman invariance . We also generalize this result to the much broader framework of Promise Valued Constraint Satisfaction Problems, which brings together two well-studied extensions of the CSP framework. Finally, we consider the hierarchies of increasingly tighter relaxations of the homomorphism and isomorphism IPs obtained by applying the Sherali-Adams and Weisfeiler-Leman methods, respectively. We extend our combinatorial characterization of the basic LP to higher levels of the Sherali-Adams hierarchy, and we generalize a well-known logical characterization of the Weisfeiler-Leman test from graphs to relational structures.Keywords
All Related Versions
Funding Information
- The European Union ((ERC, CoCoSym, 771005) and (ERC, POCOCOP, 101071674))
This publication has 69 references indexed in Scilit:
- The Complexity of the Distributed Constraint Satisfaction ProblemTheory of Computing Systems, 2022
- The wonderland of reflectionsIsrael Journal of Mathematics, 2017
- Constraints, MMSNP and expander relational structuresCombinatorica, 2013
- On recognizing graphs by numbers of homomorphismsJournal of Graph Theory, 2010
- Logical Hierarchies in PTIMEInformation and Computation, 1996
- Fractional isomorphism of graphsDiscrete Mathematics, 1994
- An optimal lower bound on the number of variables for graph identificationCombinatorica, 1992
- Describing Graphs: A First-Order Approach to Graph Canonization1990
- Graph isomorphism and theorems of Birkhoff typeComputing, 1986
- Finite common coverings of graphsJournal of Combinatorial Theory, Series B, 1982