Logarithmic Weisfeiler--Leman and Treewidth

Michael Levet, Puck Rombach, Nicholas Sieger

In this paper, we show that the $(3k+4)$-dimensional Weisfeiler--Leman algorithm can identify graphs of treewidth $k$ in $O(\log n)$ rounds. This improves the result of Grohe & Ver…