Lasserre Hierarchy for Graph Isomorphism and Homomorphism Indistinguishability
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Standard
Lasserre Hierarchy for Graph Isomorphism and Homomorphism Indistinguishability. / Roberson, David E.; Seppelt, Tim.
50th International Colloquium on Automata, Languages, and Programming, ICALP 2023. ed. / Kousha Etessami; Uriel Feige; Gabriele Puppis. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. 101 (Leibniz International Proceedings in Informatics, LIPIcs, Vol. 261).Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - GEN
T1 - Lasserre Hierarchy for Graph Isomorphism and Homomorphism Indistinguishability
AU - Roberson, David E.
AU - Seppelt, Tim
N1 - Publisher Copyright: © David E. Roberson and Tim Seppelt.
PY - 2023
Y1 - 2023
N2 - We show that feasibility of the tth 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 Lt of graphs such that graphs G and H are not distinguished by the tth level of the Lasserre hierarchy if and only if they admit the same number of homomorphisms from any graph in Lt. By analysing the treewidth of graphs in Lt we prove that the 3tth level of Sherali–Adams linear programming hierarchy is as strong as the tth 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 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 tth level of the Lasserre hierarchy with non-negativity constraints.
AB - We show that feasibility of the tth 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 Lt of graphs such that graphs G and H are not distinguished by the tth level of the Lasserre hierarchy if and only if they admit the same number of homomorphisms from any graph in Lt. By analysing the treewidth of graphs in Lt we prove that the 3tth level of Sherali–Adams linear programming hierarchy is as strong as the tth 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 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 tth level of the Lasserre hierarchy with non-negativity constraints.
KW - graph isomorphism
KW - homomorphism indistinguishability
KW - Lasserre hierarchy
KW - linear programming
KW - semidefinite programming
KW - Sherali–Adams hierarchy
KW - treewidth
U2 - 10.4230/LIPIcs.ICALP.2023.101
DO - 10.4230/LIPIcs.ICALP.2023.101
M3 - Article in proceedings
AN - SCOPUS:85167368828
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 50th International Colloquium on Automata, Languages, and Programming, ICALP 2023
A2 - Etessami, Kousha
A2 - Feige, Uriel
A2 - Puppis, Gabriele
PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik
T2 - 50th International Colloquium on Automata, Languages, and Programming, ICALP 2023
Y2 - 10 July 2023 through 14 July 2023
ER -
ID: 362936480