Document Open Access Logo

The Power of the Weisfeiler-Leman Algorithm to Decompose Graphs

Authors Sandra Kiefer , Daniel Neuen

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2019.45.pdf
  • Filesize: 494 kB
  • 15 pages

Document Identifiers

Author Details

Sandra Kiefer
  • RWTH Aachen University, Aachen, Germany
Daniel Neuen
  • RWTH Aachen University, Aachen, Germany

Cite AsGet BibTex

Sandra Kiefer and Daniel Neuen. The Power of the Weisfeiler-Leman Algorithm to Decompose Graphs. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 45:1-45:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.MFCS.2019.45

Abstract

The Weisfeiler-Leman procedure is a widely-used approach for graph isomorphism testing that works by iteratively computing an isomorphism-invariant coloring of vertex tuples. Meanwhile, a fundamental tool in structural graph theory, which is often exploited in approaches to tackle the graph isomorphism problem, is the decomposition into bi- and triconnected components. We prove that the 2-dimensional Weisfeiler-Leman algorithm implicitly computes the decomposition of a graph into its triconnected components. Thus, the dimension of the algorithm needed to distinguish two given graphs is at most the dimension required to distinguish the corresponding decompositions into 3-connected components (assuming dimension at least 2). This result implies that for k >= 2, the k-dimensional algorithm distinguishes k-separators, i.e., k-tuples of vertices that separate the graph, from other vertex k-tuples. As a byproduct, we also obtain insights about the connectivity of constituent graphs of association schemes. In an application of the results, we show the new upper bound of k on the Weisfeiler-Leman dimension of graphs of treewidth at most k. Using a construction by Cai, Fürer, and Immerman, we also provide a new lower bound that is asymptotically tight up to a factor of 2.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Combinatorial algorithms
  • Theory of computation → Finite Model Theory
  • Theory of computation → Graph algorithms analysis
Keywords
  • Weisfeiler-Leman
  • separators
  • first-order logic
  • counting quantifiers

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Stefan Arnborg, Derek G. Corneil, and Andrzej Proskurowski. Complexity of Finding Embeddings in a K-tree. SIAM J. Algebraic Discrete Methods, 8(2):277-284, April 1987. URL: http://dx.doi.org/10.1137/0608024.
  2. Vikraman Arvind, Frank Fuhlbrück, Johannes Köbler, and Oleg Verbitsky. On Weisfeiler-Leman Invariance: Subgraph Counts and Related Graph Properties. CoRR, abs/1811.04801, 2018. URL: http://arxiv.org/abs/1811.04801.
  3. Albert Atserias and Elitza N. Maneva. Sherali-Adams Relaxations and Indistinguishability in Counting Logics. SIAM J. Comput., 42(1):112-137, 2013. URL: http://dx.doi.org/10.1137/120867834.
  4. László Babai. Graph isomorphism in quasipolynomial time [extended abstract]. In Daniel Wichs and Yishay Mansour, editors, Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 684-697. ACM, 2016. URL: http://dx.doi.org/10.1145/2897518.2897542.
  5. László Babai, Xi Chen, Xiaorui Sun, Shang-Hua Teng, and John Wilmes. Faster Canonical Forms for Strongly Regular Graphs. In 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26-29 October, 2013, Berkeley, CA, USA, pages 157-166. IEEE Computer Society, 2013. URL: http://dx.doi.org/10.1109/FOCS.2013.25.
  6. Andries E. Brouwer. Spectrum and connectivity of graphs. CWI Quarterly, 9(1-2):37-40, 1996. Google Scholar
  7. Andries E. Brouwer and Jack H. Koolen. The vertex-connectivity of a distance-regular graph. Eur. J. Comb., 30(3):668-673, 2009. URL: http://dx.doi.org/10.1016/j.ejc.2008.07.006.
  8. Andries E. Brouwer and Dale M. Mesner. The Connectivity of Strongly Regular Graphs. Eur. J. Comb., 6(3):215-216, 1985. URL: http://dx.doi.org/10.1016/S0195-6698(85)80030-5.
  9. Jin-yi Cai, Martin Fürer, and Neil Immerman. An optimal lower bound on the number of variables for graph identifications. Combinatorica, 12(4):389-410, 1992. URL: http://dx.doi.org/10.1007/BF01305232.
  10. Anuj Dawar and David Richerby. The Power of Counting Logics on Restricted Classes of Finite Structures. In Jacques Duparc and Thomas A. Henzinger, editors, Computer Science Logic, 21st International Workshop, CSL 2007, 16th Annual Conference of the EACSL, Lausanne, Switzerland, September 11-15, 2007, Proceedings, volume 4646 of Lecture Notes in Computer Science, pages 84-98. Springer, 2007. URL: http://dx.doi.org/10.1007/978-3-540-74915-8_10.
  11. Holger Dell, Martin Grohe, and Gaurav Rattan. Lovász Meets Weisfeiler and Leman. In 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic, pages 40:1-40:14, 2018. URL: http://dx.doi.org/10.4230/LIPIcs.ICALP.2018.40.
  12. Reinhard Diestel. Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics. Springer, 2012. Google Scholar
  13. Sergei Evdokimov and Ilia Ponomarenko. On the vertex connectivity of a relation in an association scheme. Journal of Mathematical Sciences, 134(5):2354-2357, May 2006. URL: http://dx.doi.org/10.1007/s10958-006-0112-z.
  14. Martin Fürer. On the Combinatorial Power of the Weisfeiler-Lehman Algorithm. In Dimitris Fotakis, Aris Pagourtzis, and Vangelis Th. Paschos, editors, Algorithms and Complexity - 10th International Conference, CIAC 2017, Athens, Greece, May 24-26, 2017, Proceedings, volume 10236 of Lecture Notes in Computer Science, pages 260-271, 2017. URL: http://dx.doi.org/10.1007/978-3-319-57586-5_22.
  15. Martin Grohe. Fixed-point definability and polynomial time on graphs with excluded minors. J. ACM, 59(5):27:1-27:64, 2012. URL: http://dx.doi.org/10.1145/2371656.2371662.
  16. Martin Grohe. Descriptive Complexity, Canonisation, and Definable Graph Structure Theory. Lecture Notes in Logic. Cambridge University Press, 2017. Google Scholar
  17. Martin Grohe and Sandra Kiefer. A Linear Upper Bound on the Weisfeiler-Leman Dimension of Graphs of Bounded Genus. CoRR, abs/1904.07216, 2019. URL: http://arxiv.org/abs/1904.07216.
  18. Martin Grohe and Julian Mariño. Definability and Descriptive Complexity on Databases of Bounded Tree-Width. In Catriel Beeri and Peter Buneman, editors, Database Theory - ICDT '99, 7th International Conference, Jerusalem, Israel, January 10-12, 1999, Proceedings., volume 1540 of Lecture Notes in Computer Science, pages 70-82. Springer, 1999. URL: http://dx.doi.org/10.1007/3-540-49257-7_6.
  19. Martin Grohe and Daniel Neuen. Canonisation and Definability for Graphs of Bounded Rank Width. CoRR, abs/1901.10330, 2019. URL: http://arxiv.org/abs/1901.10330.
  20. Martin Grohe and Martin Otto. Pebble Games and linear equations. J. Symb. Log., 80(3):797-844, 2015. URL: http://dx.doi.org/10.1017/jsl.2015.28.
  21. Lauri Hella. Logical Hierarchies in PTIME. Inf. Comput., 129(1):1-19, 1996. URL: http://dx.doi.org/10.1006/inco.1996.0070.
  22. John E. Hopcroft and Robert Endre Tarjan. A V² Algorithm for Determining Isomorphism of Planar Graphs. Inf. Process. Lett., 1(1):32-34, 1971. URL: http://dx.doi.org/10.1016/0020-0190(71)90019-6.
  23. John E. Hopcroft and Robert Endre Tarjan. Isomorphism of Planar Graphs. In Raymond E. Miller and James W. Thatcher, editors, Proceedings of a symposium on the Complexity of Computer Computations, held March 20-22, 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York, USA, The IBM Research Symposia Series, pages 131-152. Plenum Press, New York, 1972. Google Scholar
  24. John E. Hopcroft and Robert Endre Tarjan. A V log V Algorithm for Isomorphism of Triconnected Planar Graphs. J. Comput. Syst. Sci., 7(3):323-331, 1973. URL: http://dx.doi.org/10.1016/S0022-0000(73)80013-3.
  25. John E. Hopcroft and Robert Endre Tarjan. Dividing a Graph into Triconnected Components. SIAM J. Comput., 2(3):135-158, 1973. URL: http://dx.doi.org/10.1137/0202012.
  26. John E. Hopcroft and J. K. Wong. Linear Time Algorithm for Isomorphism of Planar Graphs (Preliminary Report). In Robert L. Constable, Robert W. Ritchie, Jack W. Carlyle, and Michael A. Harrison, editors, Proceedings of the 6th Annual ACM Symposium on Theory of Computing, April 30 - May 2, 1974, Seattle, Washington, USA, pages 172-184. ACM, 1974. URL: http://dx.doi.org/10.1145/800119.803896.
  27. Neil Immerman and Eric Lander. Describing Graphs: A First-Order Approach to Graph Canonization. In Complexity Theory Retrospective, pages 59-81. Springer New York, 1990. URL: http://dx.doi.org/10.1007/978-1-4612-4478-3_5.
  28. Sandra Kiefer and Daniel Neuen. The power of the Weisfeiler-Leman algorithm to decompose graphs. CoRR, abs/1908.05268, 2019. URL: http://arxiv.org/abs/1908.05268.
  29. Sandra Kiefer, Ilia Ponomarenko, and Pascal Schweitzer. The Weisfeiler-Leman dimension of planar graphs is at most 3. In 32nd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2017, Reykjavik, Iceland, June 20-23, 2017, pages 1-12. IEEE Computer Society, 2017. URL: http://dx.doi.org/10.1109/LICS.2017.8005107.
  30. Brian G. Kodalen and William J. Martin. On the Connectivity of Graphs in Association Schemes. Electr. J. Comb., 24(4):P4.39, 2017. URL: http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i4p39.
  31. Brendan D. McKay. Practical graph isomorphism. Congr. Numer., 30:45-87, 1981. Google Scholar
  32. Brendan D. McKay and Adolfo Piperno. Practical graph isomorphism, II. J. Symb. Comput., 60:94-112, 2014. URL: http://dx.doi.org/10.1016/j.jsc.2013.09.003.
  33. Christopher Morris and Petra Mutzel. Towards a practical k-dimensional Weisfeiler-Leman algorithm. CoRR, abs/1904.01543, 2019. URL: http://arxiv.org/abs/1904.01543.
  34. Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks. CoRR, abs/1810.02244, 2018. URL: http://arxiv.org/abs/1810.02244.
  35. Daniel Neuen. Graph Isomorphism for Unit Square Graphs. In Piotr Sankowski and Christos D. Zaroliagis, editors, 24th Annual European Symposium on Algorithms, ESA 2016, August 22-24, 2016, Aarhus, Denmark, volume 57 of LIPIcs, pages 70:1-70:17. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.ESA.2016.70.
  36. William T. Tutte. Graph theory. Encyclopedia of mathematics and its applications. Addison-Wesley Pub. Co., Advanced Book Program, 1984. Google Scholar
  37. Boris Weisfeiler and A. Leman. The reduction of a graph to canonical form and the algebra which appears therein. NTI, Series 2, 1968. English translation by G. Ryabov available at URL: https://www.iti.zcu.cz/wl2018/pdf/wl_paper_translation.pdf.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact