2026-08-16T16:23:31Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20072 2024-05-31T13:11:12Z ddc:004 open_access

Canonizing Graphs of Bounded Rank-Width in Parallel via Weisfeiler-Leman Levet, Michael Rombach, Puck Sieger, Nicholas Graph Isomorphism Weisfeiler-Leman Rank-Width Canonization Descriptive Complexity Circuit Complexity In this paper, we show that computing canonical labelings of graphs of bounded rank-width is in TC². Our approach builds on the framework of Köbler & Verbitsky (CSR 2008), who established the analogous result for graphs of bounded treewidth. Here, we use the framework of Grohe & Neuen (ACM Trans. Comput. Log., 2023) to enumerate separators via split-pairs and flip functions. In order to control the depth of our circuit, we leverage the fact that any graph of rank-width k admits a rank decomposition of width ≤ 2k and height O(log n) (Courcelle & Kanté, WG 2007). This allows us to utilize an idea from Wagner (CSR 2011) of tracking the depth of the recursion in our computation. Furthermore, after splitting the graph into connected components, it is necessary to decide isomorphism of said components in TC¹. To this end, we extend the work of Grohe & Neuen (ibid.) to show that the (6k+3)-dimensional Weisfeiler-Leman (WL) algorithm can identify graphs of rank-width k using only O(log n) rounds. As a consequence, we obtain that graphs of bounded rank-width are identified by FO + C formulas with 6k+4 variables and quantifier depth O(log n). Prior to this paper, isomorphism testing for graphs of bounded rank-width was not known to be in NC. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Michael Levet and Puck Rombach and Nicholas Sieger 2024 Is Part Of LIPIcs, Volume 294, 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SWAT.2024.32 urn:nbn:de:0030-drops-200724 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.32 eng https://creativecommons.org/licenses/by/4.0/legalcode