Canonizing Graphs of Bounded Rank-Width in Parallel via Weisfeiler--Leman

MaRDI QIDQ6510854arXivFDO

Authors Michael Levet, Puck Rombach, Nicholas Sieger

Published in arXiv

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 extend the work of Grohe & Neuen (ACM T. Comput. Log., 2023) to show that the $(6k+3)$-dimensional Weisfeiler--Leman (WL) algorithm can identify graphs of rank width $k$ using only $O(logn)$ rounds. As a consequence, we obtain that graphs of bounded rank width are identified by $extsfFO+extsfC$ formulas with $6k+4$ variables and quantifier depth $O(logn)$. Furthermore, in light of the parallel WL implementation due to Grohe & Verbitsky (ICALP 2006), we obtain $extsf{TC}^1$ upper bounds for isomorphism testing of graphs of bounded rank width. Prior to this paper, isomorphism testing for graphs of bounded rank width was not known to be in $extsfNC$.

This page was built for publication: Canonizing Graphs of Bounded Rank-Width in Parallel via Weisfeiler--Leman

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