Logarithmic Weisfeiler--Leman and Treewidth

MaRDI QIDQ6429555zbMATH OpenFDO

Authors Michael Levet, Puck Rombach, Nicholas Sieger

Publication date 14 March 2023

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Descriptive complexity and finite models (68Q19) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Abstract: In this paper, we show that the $(3k+4)$-dimensional Weisfeiler--Leman algorithm can identify graphs of treewidth $k$ in $O(logn)$ 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 $extsfFO+extsfC$ (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 $extsfFO+extsfC$ with quantifier depth $O(logn)$ that identifies $G$ up to isomorphism.

This page was built for publication: Logarithmic Weisfeiler--Leman and Treewidth

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6429555)