Current browse context:
cs.DS
Change to browse by:
References & Citations
Computer Science > Data Structures and Algorithms
Title: Logarithmic Weisfeiler--Leman and Treewidth
(Submitted on 14 Mar 2023 (v1), last revised 24 Apr 2024 (this version, v2))
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 $\textsf{FO} + \textsf{C}$ (Cai, F\"urer, & 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 $\varphi$ in $\textsf{FO} + \textsf{C}$ with quantifier depth $O(\log n)$ that identifies $G$ up to isomorphism.
Submission history
From: Michael Levet [view email][v1] Tue, 14 Mar 2023 15:41:47 GMT (18kb)
[v2] Wed, 24 Apr 2024 19:54:50 GMT (0kb,I)
Link back to: arXiv, form interface, contact.