Logarithmic Weisfeiler--Leman and Treewidth

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 & Verbitsky (ICALP 2006), who previously established the analogous result for $(4k+3)$-dimensional Weisfeiler–Leman. In light of the equivalence between Weisfeiler–Leman and the logic $\mathsf{\text{FO}}+\mathsf{\text{C}}$ (Cai, Fürer, & Immerman, Combinatorica 1992), we obtain an improvement in the descriptive complexity for graphs of treewidth $k$. Precisely, if $G$ is a graph of treewidth $k$, then there exists a $(3k+5)$-variable formula $\phi$ in $\mathsf{\text{FO}}+\mathsf{\text{C}}$ with quantifier depth $O(\log n)$ that identifies $G$ up to isomorphism.