Lasserre Hierarchy for Graph Isomorphism and Homomorphism Indistinguishability

Publikation: Bidrag til bog/antologi/rapportKonferencebidrag i proceedingsForskningfagfællebedømt

Dokumenter

  • Fulltext

    Forlagets udgivne version, 893 KB, PDF-dokument

  • David E. Roberson
  • Tim Seppelt

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.

OriginalsprogEngelsk
Titel50th International Colloquium on Automata, Languages, and Programming, ICALP 2023
RedaktørerKousha Etessami, Uriel Feige, Gabriele Puppis
Antal sider18
ForlagSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Publikationsdato2023
Artikelnummer101
ISBN (Elektronisk)9783959772785
DOI
StatusUdgivet - 2023
Begivenhed50th International Colloquium on Automata, Languages, and Programming, ICALP 2023 - Paderborn, Tyskland
Varighed: 10 jul. 202314 jul. 2023

Konference

Konference50th International Colloquium on Automata, Languages, and Programming, ICALP 2023
LandTyskland
ByPaderborn
Periode10/07/202314/07/2023
SponsorDeepL, et al., Paderborn Center for Parallel Computing (PC2), REPLY, SFB 901, Stiebel Eltron
NavnLeibniz International Proceedings in Informatics, LIPIcs
Vol/bind261
ISSN1868-8969

Bibliografisk note

Funding Information:
Funding David E. Roberson: Supported by the Carlsberg Foundation Young Researcher Fellowship CF21-0682 – “Quantum Graph Theory”. Tim Seppelt: German Research Council (DFG) within Research Training Group 2236 (UnRAVeL) Acknowledgements Initial discussions for this work took place at Dagstuhl Seminar 22051 “Finite and Algorithmic Model Theory”.

Funding Information:
David E. Roberson: Supported by the Carlsberg Foundation Young Researcher Fellowship CF21-0682 – “Quantum Graph Theory”. Tim Seppelt: German Research Council (DFG) within Research Training Group 2236 (UnRAVeL)

Publisher Copyright:
© David E. Roberson and Tim Seppelt.

ID: 362936480