LIPIcs.ICALP.2023.101.pdf
- Filesize: 0.87 MB
- 18 pages
Document
Lasserre Hierarchy for Graph Isomorphism and Homomorphism Indistinguishability
Authors
David E. Roberson 
,
Tim Seppelt
-
Part of:
Volume:
50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Colloquium on Automata, Languages, and Programming (ICALP) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2023-07-05
File
Document Identifiers
Author Details
- Department of Applied Mathematics and Computer Science, Technical University of Denmark, Copenhagen, Denmark
- QMATH, Department of Mathematical Sciences, University of Copenhagen, Denmark
Acknowledgements
Initial discussions for this work took place at Dagstuhl Seminar 22051 "Finite and Algorithmic Model Theory".
Cite As Get BibTex
David E. Roberson and Tim Seppelt. Lasserre Hierarchy for Graph Isomorphism and Homomorphism Indistinguishability. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 101:1-101:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.ICALP.2023.101
Abstract
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.
Subject Classification
ACM Subject Classification
- Mathematics of computing → Combinatorics
- Mathematics of computing → Graph theory
Keywords
- Lasserre hierarchy
- homomorphism indistinguishability
- Sherali-Adams hierarchy
- treewidth
- semidefinite programming
- linear programming
- graph isomorphism
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Samson Abramsky, Tomáš Jakl, and Thomas Paine. Discrete density comonads and graph parameters. In Helle Hvid Hansen and Fabio Zanasi, editors, Coalgebraic Methods in Computer Science - 16th IFIP WG 1.3 International Workshop, CMCS 2022, Colocated with ETAPS 2022, Munich, Germany, April 2-3, 2022, Proceedings, volume 13225 of Lecture Notes in Computer Science, pages 23-44. Springer, 2022. URL: https://doi.org/10.1007/978-3-031-10736-8_2.
- Albert Atserias, Phokion G. Kolaitis, and Wei-Lin Wu. On the expressive power of homomorphism counts. In 36th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2021, Rome, Italy, June 29 - July 2, 2021, pages 1-13. IEEE, 2021. URL: https://doi.org/10.1109/LICS52264.2021.9470543.
- Albert Atserias and Elitza Maneva. Sherali-Adams Relaxations and Indistinguishability in Counting Logics. SIAM Journal on Computing, 42(1):112-137, 2013. URL: https://doi.org/10.1137/120867834.
- Albert Atserias and Joanna Ochremiak. Definable Ellipsoid Method, Sums-of-Squares Proofs, and the Isomorphism Problem. In Anuj Dawar and Erich Grädel, editors, Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2018, Oxford, UK, July 09-12, 2018, pages 66-75. ACM, 2018. URL: https://doi.org/10.1145/3209108.3209186.
- Christoph Berkholz and Martin Grohe. Limitations of Algebraic Approaches to Graph Isomorphism Testing. In Magnús M. Halldórsson, Kazuo Iwama, Naoki Kobayashi, and Bettina Speckmann, editors, Automata, Languages, and Programming, pages 155-166. Springer Berlin Heidelberg, 2015. URL: https://doi.org/10.1007/978-3-662-47672-7_13.
- Jin-Yi Cai, Martin Fürer, and Neil Immerman. An optimal lower bound on the number of variables for graph identification. Combinatorica, 12(4):389-410, 1992. URL: https://doi.org/10.1007/BF01305232.
- Gang Chen and Ilia Ponomarenko. Lectures on Coherent Configurations. Central China Normal University Press, Wuhan, 2018. URL: https://www.pdmi.ras.ru/~inp/ccNOTES.pdf.
- Anuj Dawar, Tomáš Jakl, and Luca Reggio. Lovász-Type Theorems and Game Comonads. In 36th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2021, Rome, Italy, June 29 - July 2, 2021, pages 1-13. IEEE, 2021. URL: https://doi.org/10.1109/LICS52264.2021.9470609.
- Holger Dell, Martin Grohe, and Gaurav Rattan. Lovász Meets Weisfeiler and Leman. 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), pages 40:1-40:14, 2018. URL: https://doi.org/10.4230/LIPICS.ICALP.2018.40.
- Zdeněk Dvořák. On recognizing graphs by numbers of homomorphisms. Journal of Graph Theory, 64(4):330-342, August 2010. URL: https://doi.org/10.1002/jgt.20461.
- Martin Grohe. Counting Bounded Tree Depth Homomorphisms. In Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS '20, pages 507-520, New York, NY, USA, 2020. Association for Computing Machinery. URL: https://doi.org/10.1145/3373718.3394739.
- Martin Grohe. word2vec, node2vec, graph2vec, X2vec: Towards a Theory of Vector Embeddings of Structured Data. In Dan Suciu, Yufei Tao, and Zhewei Wei, editors, Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2020, Portland, OR, USA, June 14-19, 2020, pages 1-16. ACM, 2020. URL: https://doi.org/10.1145/3375395.3387641.
- Martin Grohe and Martin Otto. Pebble Games and Linear Equations. The Journal of Symbolic Logic, 80(3):797-844, 2015. URL: https://doi.org/10.1017/jsl.2015.28.
- Martin Grohe, Gaurav Rattan, and Tim Seppelt. Homomorphism Tensors and Linear Equations, 2021. URL: https://doi.org/10.48550/arXiv.2111.11313.
- Martin Grohe, Gaurav Rattan, and Tim Seppelt. Homomorphism Tensors and Linear Equations. In Mikołaj Bojańczyk, Emanuela Merelli, and David P. Woodruff, editors, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022), volume 229 of Leibniz International Proceedings in Informatics (LIPIcs), pages 70:1-70:20, Dagstuhl, Germany, 2022. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.ICALP.2022.70.
- Martin Grotschel. Geometric Algorithms and Combinatorial Optimization. Springer Berlin Heidelberg, 2012. URL: https://doi.org/10.1007/978-3-642-97881-4.
- Jean B. Lasserre. Global Optimization with Polynomials and the Problem of Moments. SIAM Journal on Optimization, 11(3):796-817, 2001. URL: https://doi.org/10.1137/S1052623400366802.
- Monique Laurent. A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0-1 Programming. Mathematics of Operations Research, 28(3):470-496, 2003. URL: http://www.jstor.org/stable/4126981.
- László Lovász. Operations with structures. Acta Mathematica Academiae Scientiarum Hungarica, 18(3):321-328, September 1967. URL: https://doi.org/10.1007/BF02280291.
- Laura Mančinska and David E. Roberson. Quantum isomorphism is equivalent to equality of homomorphism counts from planar graphs. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 661-672, 2020. URL: https://doi.org/10.1109/FOCS46700.2020.00067.
- Laura Mančinska, David E. Roberson, Robert Samal, Simone Severini, and Antonios Varvitsiotis. Relaxations of Graph Isomorphism. In Ioannis Chatzigiannakis, Piotr Indyk, Fabian Kuhn, and Anca Muscholl, editors, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017), volume 80 of Leibniz International Proceedings in Informatics (LIPIcs), pages 76:1-76:14, Dagstuhl, Germany, 2017. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.ICALP.2017.76.
- Laura Mančinska, David E. Roberson, and Antonios Varvitsiotis. Graph isomorphism: Physical resources, optimization models, and algebraic characterizations, 2020-04-22. URL: https://doi.org/10.48550/arXiv.2004.10893.
- Yoàv Montacute and Nihil Shah. The pebble-relation comonad in finite model theory. In Christel Baier and Dana Fisman, editors, LICS '22: 37th Annual ACM/IEEE Symposium on Logic in Computer Science, Haifa, Israel, August 2 - 5, 2022, pages 13:1-13:11. ACM, 2022. URL: https://doi.org/10.1145/3531130.3533335.
- Daniel Neuen. Homomorphism-Distinguishing Closedness for Graphs of Bounded Tree-Width, April 2023. URL: https://doi.org/10.48550/arXiv.2304.07011.
- Ryan O'Donnell, John Wright, Chenggang Wu, and Yuan Zhou. Hardness of Robust Graph Isomorphism, Lasserre Gaps, and Asymmetry of Random Graphs. In Chandra Chekuri, editor, Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 1659-1677. SIAM, 2014. URL: https://doi.org/10.1137/1.9781611973402.120.
- Gaurav Rattan and Tim Seppelt. Weisfeiler-Leman and Graph Spectra. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2268-2285, 2023. URL: https://doi.org/10.1137/1.9781611977554.ch87.
- David E. Roberson. Oddomorphisms and homomorphism indistinguishability over graphs of bounded degree, June 2022. URL: https://doi.org/10.48550/arXiv.2206.10321.
- David E. Roberson and Tim Seppelt. Lasserre Hierarchy for Graph Isomorphism and Homomorphism Indistinguishability, 2023. URL: https://doi.org/10.48550/ARXIV.2302.10538.
- N. Robertson and P.D. Seymour. Graph Minors XIII. The Disjoint Paths Problem. Journal of Combinatorial Theory, Series B, 63(1):65-110, 1995. URL: https://doi.org/10.1006/jctb.1995.1006.
- Tim Seppelt. Logical Equivalences, Homomorphism Indistinguishability, and Forbidden Minors, February 2023. URL: https://doi.org/10.48550/ARXIV.2302.11290.
- P.D. Seymour and R. Thomas. Graph Searching and a Min-Max Theorem for Tree-Width. Journal of Combinatorial Theory, Series B, 58(1):22-33, 1993. URL: https://doi.org/10.1006/jctb.1993.1027.
- Hanif D. Sherali and Warren P. Adams. A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems. SIAM Journal on Discrete Mathematics, 3(3):411-430, 1990. URL: https://doi.org/10.1137/0403036.
- Aaron Snook, Grant Schoenebeck, and Paolo Codenotti. Graph Isomorphism and the Lasserre Hierarchy, 2014. URL: https://doi.org/10.48550/arXiv.1401.0758.
- Maciej M. Sysło. Characterizations of outerplanar graphs. Discrete Mathematics, 26(1):47-53, 1979. URL: https://doi.org/10.1016/0012-365X(79)90060-8.
- Edwin R. van Dam and Willem H. Haemers. Which graphs are determined by their spectrum? Linear Algebra and its Applications, 373:241-272, 2003. URL: https://doi.org/10.1016/S0024-3795(03)00483-X.
- Boris Weisfeiler. On Construction and Identification of Graphs, volume 558 of Lecture Notes in Mathematics. Springer Berlin Heidelberg, Berlin, Heidelberg, 1976. URL: https://doi.org/10.1007/BFb0089374.