Decomposing and Identifying Graphs with Weisfeiler and Leman

Prelegent(ci)

Sandra Kiefer

Afiliacja

MIM UW

Termin

31 marca 2021 14:15

Informacje na temat wydarzenia

online

Seminarium

Seminarium „Teoria automatów”

---

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.

---