You are not logged in | Log in

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.