Lasserre Hierarchy for Graph Isomorphism and Homomorphism Indistinguishability
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929493202960384 |
|---|---|
| author | Roberson, David E. Seppelt, Tim |
| author_facet | Roberson, David E. Seppelt, Tim |
| contents | We show that feasibility of the $t^\text{th}$ level of the Lasserre semidefinite programming hierarchy for graph isomorphism can be expressed as a homomorphism indistinguishability relation. In other words, we define a class $\mathcal{L}_t$ of graphs such that graphs $G$ and $H$ are not distinguished by the $t^\text{th}$ level of the Lasserre hierarchy if and only if they admit the same number of homomorphisms from any graph in $\mathcal{L}_t$. By analysing the treewidth of graphs in $\mathcal{L}_t$, we prove that the $3t^\text{th}$ level of Sherali--Adams linear programming hierarchy is as strong as the $t^\text{th}$ level of Lasserre. Moreover, we show that this is best possible in the sense that $3t$ cannot be lowered to $3t-1$ for any $t$. The same result holds for the Lasserre hierarchy with non-negativity constraints, which we similarly characterise in terms of homomorphism indistinguishability over a family $\mathcal{L}_t^+$ of graphs. Additionally, we give characterisations of level-$t$ Lasserre with non-negativity constraints in terms of logical equivalence and via a graph colouring algorithm akin to the Weisfeiler--Leman algorithm. This provides a polynomial time algorithm for determining if two given graphs are distinguished by the $t^\text{th}$ level of the Lasserre hierarchy with non-negativity constraints. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2302_10538 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Lasserre Hierarchy for Graph Isomorphism and Homomorphism Indistinguishability Roberson, David E. Seppelt, Tim Combinatorics Computational Complexity Discrete Mathematics Logic in Computer Science Optimization and Control We show that feasibility of the $t^\text{th}$ level of the Lasserre semidefinite programming hierarchy for graph isomorphism can be expressed as a homomorphism indistinguishability relation. In other words, we define a class $\mathcal{L}_t$ of graphs such that graphs $G$ and $H$ are not distinguished by the $t^\text{th}$ level of the Lasserre hierarchy if and only if they admit the same number of homomorphisms from any graph in $\mathcal{L}_t$. By analysing the treewidth of graphs in $\mathcal{L}_t$, we prove that the $3t^\text{th}$ level of Sherali--Adams linear programming hierarchy is as strong as the $t^\text{th}$ level of Lasserre. Moreover, we show that this is best possible in the sense that $3t$ cannot be lowered to $3t-1$ for any $t$. The same result holds for the Lasserre hierarchy with non-negativity constraints, which we similarly characterise in terms of homomorphism indistinguishability over a family $\mathcal{L}_t^+$ of graphs. Additionally, we give characterisations of level-$t$ Lasserre with non-negativity constraints in terms of logical equivalence and via a graph colouring algorithm akin to the Weisfeiler--Leman algorithm. This provides a polynomial time algorithm for determining if two given graphs are distinguished by the $t^\text{th}$ level of the Lasserre hierarchy with non-negativity constraints. |
| title | Lasserre Hierarchy for Graph Isomorphism and Homomorphism Indistinguishability |
| topic | Combinatorics Computational Complexity Discrete Mathematics Logic in Computer Science Optimization and Control |
| url | https://arxiv.org/abs/2302.10538 |