Decomposing and Identifying Graphs with Weisfeiler and Leman

Speaker(s)

Sandra Kiefer

Affiliation

MIM UW

Date

March 31, 2021, 2:15 p.m.

Information about the event

online

Seminar

Seminar Automata Theory

---

The Weisfeiler-Leman (WL) procedure is a widely-used approach for graph-isomorphism testing. It works by iteratively computing an isomorphism-invariant coloring of vertex tuples. Meanwhile, decompositions are a fundamental tool in structural graph theory and often exploited in approaches to tackle the graph-isomorphism problem. In this talk, I discuss the ability of the WL algorithm to identify graphs by decomposing them into trees. In particular, I give an overview of our proof that the 2-dimensional WL algorithm (2-WL) implicitly computes the decomposition of a graph into its 3-connected components. This quite technical statement allows us to draw strong conclusions for the class of graphs of bounded treewidth and the class of planar graphs.

---