The Sherali-Adams and Weisfeiler-Leman hierarchies in (Promise Valued) Constraint Satisfaction Problems
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916110366932992 |
|---|---|
| author | Barto, Libor Butti, Silvia Dalmau, Víctor |
| author_facet | Barto, Libor Butti, Silvia Dalmau, Víctor |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_16998 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The Sherali-Adams and Weisfeiler-Leman hierarchies in (Promise Valued) Constraint Satisfaction Problems Barto, Libor Butti, Silvia Dalmau, Víctor Data Structures and Algorithms Logic in Computer Science 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. |
| title | The Sherali-Adams and Weisfeiler-Leman hierarchies in (Promise Valued) Constraint Satisfaction Problems |
| topic | Data Structures and Algorithms Logic in Computer Science |
| url | https://arxiv.org/abs/2401.16998 |