Logarithmic Weisfeiler--Leman and Treewidth

Abstract

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 $\text{FO}+\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 $\ddot{I}†$ in $\text{FO}+\text{C}$ with quantifier depth $O(\log n)$ that identifies $G$ up to isomorphism.

There were minor bugs in this version. We corrected those bugs and folded this result into a different paper: arXiv:2306.17777