The Sherali-Adams and Weisfeiler-Leman hierarchies in (Promise Valued) Constraint Satisfaction Problems
Preprint
Abstract
In this paper 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
This publication has 34 references indexed in Scilit:
- Sherali–Adams relaxations of graph isomorphism polytopesDiscrete Optimization, 2014
- 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
- An optimal lower bound on the number of variables for graph identificationCombinatorica, 1992
- A note on compact graphsDiscrete Applied Mathematics, 1991
- Describing Graphs: A First-Order Approach to Graph Canonization1990
- Chromatically optimal rigid graphsJournal of Combinatorial Theory, Series B, 1989
- Graph isomorphism and theorems of Birkhoff typeComputing, 1986
- Graph minors. III. Planar tree-widthJournal of Combinatorial Theory, Series B, 1984