English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

In this paper, we show that computing canonical labelings of graphs ofbounded rank-width is in $\textsf{TC}^{2}$. Our approach builds on theframework of K\"obler & Verbitsky (CSR 2008), who established the analogousresult for graphs of bounded treewidth. Here, we use the framework of Grohe &Neuen (ACM Trans. Comput. Log., 2023) to enumerate separators via split-pairsand flip functions. In order to control the depth of our circuit, we leveragethe fact that any graph of rank-width $k$ admits a rank decomposition of width$\leq 2k$ and height $O(\log n)$ (Courcelle & Kant\'e, WG 2007). This allows usto utilize an idea from Wagner (CSR 2011) of tracking the depth of therecursion in our computation.  Furthermore, after splitting the graph into connected components, it isnecessary to decide isomorphism of said components in $\textsf{TC}^{1}$. Tothis end, we extend the work of Grohe & Neuen (ibid.) to show that the$(6k+3)$-dimensional Weisfeiler--Leman (WL) algorithm can identify graphs ofrank-width $k$ using only $O(\log n)$ rounds. As a consequence, we obtain thatgraphs of bounded rank-width are identified by $\textsf{FO} + \textsf{C}$formulas with $6k+4$ variables and quantifier depth $O(\log n)$.  Prior to this paper, isomorphism testing for graphs of bounded rank-width wasnot known to be in $\textsf{NC}$.

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