2026-07-22T13:39:16Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18153 2024-03-06T11:01:10Z ddc:004 open_access

Lasserre Hierarchy for Graph Isomorphism and Homomorphism Indistinguishability Roberson, David E. Seppelt, Tim Lasserre hierarchy homomorphism indistinguishability Sherali-Adams hierarchy treewidth semidefinite programming linear programming graph isomorphism We show that feasibility of the t^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 ℒ_t of graphs such that graphs G and H are not distinguished by the t^th level of the Lasserre hierarchy if and only if they admit the same number of homomorphisms from any graph in ℒ_t. By analysing the treewidth of graphs in ℒ_t we prove that the 3t^th level of Sherali-Adams linear programming hierarchy is as strong as the t^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 ℒ_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^th level of the Lasserre hierarchy with non-negativity constraints. Schloss Dagstuhl – Leibniz-Zentrum für Informatik David E. Roberson and Tim Seppelt 2023 Is Part Of LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2023.101 urn:nbn:de:0030-drops-181531 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.101 eng https://creativecommons.org/licenses/by/4.0/legalcode