# Logarithmic Weisfeiler–Leman Identifies All Graphs of
Bounded Rank Width111This work was completed in part at the 2022 Graduate
Research Workshop in Combinatorics, which was supported in part by NSF grant
#1953985 and a generous award from the Combinatorics Foundation. ML was
partially supported by J. A. Grochow’s NSF award CISE-2047756 and the
University of Colorado Boulder, Department of Computer Science Summer Research
Fellowship.

Michael Levet  Department of Computer Science, College of Charleston
Department of Computer Science, University of Colorado Boulder  Nicholas
Sieger  Department of Mathematics, University of California San Diego

###### 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(\log n)$ rounds. As a
consequence, we obtain that graphs of bounded rank width are identified by
$\textsf{FO}+\textsf{C}$ formulas with $6k+4$ variables and quantifier depth
$O(\log n)$. Furthermore, in light of the parallel WL implementation due to
Grohe & Verbitsky (ICALP 2006), we obtain $\textsf{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
NC.

##  1 Introduction

The Graph Isomorphism problem (GI) takes as input two graphs $G$ and $H$, and
asks if there exists an isomorphism $\varphi:V(G)\to V(H)$. GI is in
particular conjectured to be NP-intermediate; that is, belonging to NP but
neither in P nor NP-complete [Lad75]. Algorithmically, the best known upper-
bound is $n^{\Theta(\log^{2}n)}$, due to Babai [Bab16]. It remains open as to
whether GI belongs to P. There is considerable evidence suggesting that GI is
not NP-complete [Sch88, BH92, IPZ01, Bab16, KST92, AK06, Mat79]. Recent works
[FGS19, GQ19] have established that for any field $\mathbb{F}$, GI belongs to
$\mathbb{F}$-Tensor Isomorphism ($\textsf{TI}_{\mathbb{F}}$). When
$\mathbb{F}$ is finite,
$\textsf{TI}_{\mathbb{F}}\subseteq\textsf{NP}\cap\textsf{coAM}$.222We refer
the reader to [GQ19, Remark 3.4] for discussion on $\textsf{TI}_{\mathbb{F}}$
when $\mathbb{F}$ is infinite. In contrast, the best known lower-bound for GI
is DET [Tor04], which contains NL and is a subclass of $\textsf{TC}^{1}$. It
is thus natural to inquire as to families of graphs where isomorphism testing
is decidable in complexity classes contained within DET.

There has been considerable work on efficient algorithms for several families
of graphs. In particular, polynomial-time isomorphism tests are known for
several families of graphs such as graphs of bounded degree [Luk82, BKL83,
BL83, FSS83, GNS0], planar graphs [KPS19, GK21, DLN+09], graphs of bounded
genus [Gro17, GK19], graphs of bounded tree width [GV06], all classes
excluding a fixed graph as a minor [Pon91, Gro12] or even a topological
subgraph [GM15], and recently graphs of bounded rank width [GS15, GN23]. The
cases of planar graphs [Lin92, DLN+09, JKMT03], graphs of bounded genus
[EK14], and graphs of bounded treewidth [ES17] are even known to be
L-complete.

The $k$-dimensional Weisfeiler–Leman algorithm ($k$-WL) serves as a key
combinatorial tool in GI. It works by iteratively coloring $k$-tuples of
vertices in an isomorphism-invariant manner. On its own, Weisfeiler–Leman
serves as an efficient polynomial-time isomorphism test for several families
of graphs, including trees [Edm65, IL90], planar graphs [KPS19, GK21], graphs
of bounded genus [Gro00, GK19], and graphs for which a specified minor $H$ is
forbidden [Gro12]. We also note that $1$-WL identifies almost all graphs
[BK79, BES80] and $2$-WL identifies almost all regular graphs [Bol82, Kuc87].
In the case of graphs of bounded treewidth [GV06, LRS23] and planar graphs
[GV06, Ver07, GK21], Weisfeiler–Leman serves even as an NC isomorphism test.
Despite the success of WL as an isomorphism test, it is insufficient to place
GI into P [CFI92, NS18]. Nonetheless, WL remains an active area of research.
For instance, Babai’s quasipolynomial-time algorithm [Bab16] combines $O(\log
n)$-WL with group theoretic techniques.

Graphs of bounded rank width have only recently received attention from the
perspective of isomorphism testing. Grohe & Schweitzer [GS15] gave the first
polynomial-time isomorphism test for graphs of bounded rank width. In
particular, their isomorphism test ran in time $n^{f(k)}$, where $f(k)$ was a
non-elementary function of the rank width $k$. Subsequently, Grohe & Neuen
[GN23] showed that graphs of rank width $k$ have Weisfeiler–Leman dimension
$\leq 3k+5$, which yields an $O(n^{3k+6}\log n)$-time isomorphism test. In
particular, it is open as to whether graphs of bounded rank width admit NC or
FPT isomorphism tests. This is in contrast to graphs of bounded treewidth,
where NC [GV06, KV08, Wag11, DTW12, ES17, LRS23] and FPT [LPPS17, GNSW20]
isomorphism tests are well-known.

Main Results. In this paper, we investigate the parallel and descriptive
complexities of identifying graphs of bounded rank width, using the
Weisfeiler–Leman algorithm.

######  Theorem 1.1.

The $(6k+3)$-dimensional Weisfeiler–Leman algorithm identifies graphs of rank
width $k$ in $O(\log n)$ rounds.

Combining Theorem 1.1 with the parallel WL implementation of Grohe & Verbitsky
[GV06], we obtain the first NC bound for isomorphism testing of graphs of
bounded rank width.

######  Corollary 1.2.

Let $G$ be a graph of rank width $O(1)$, and let $H$ be arbitrary. We can
decide isomorphism between $G$ and $H$ in $\textsf{TC}^{1}$.

Furthermore, in light of the close connections between Weisfeiler–Leman and
$\textsf{FO}+\textsf{C}$ [IL90, CFI92], we obtain the following corollary.

######  Corollary 1.3.

For every graph $G$ of rank width at most $k$, there is a sentence
$\varphi_{G}\in\mathcal{C}_{6k+4,O(\log n)}$ that characterizes $G$ up to
isomorphism. That is, whenever $H\not\cong G$, we have that
$G\models\varphi_{G}$ and $H\not\models\varphi_{G}$.

##  2 Preliminaries

###  2.1 Weisfeiler–Leman

We begin by recalling the Weisfeiler–Leman algorithm for graphs, which
computes an isomorphism-invariant coloring. Let $G$ be a graph, and let $k\geq
2$ be an integer. The $k$-dimension Weisfeiler–Leman, or $k$-WL, algorithm
begins by constructing an initial coloring $\chi_{0}:V(G)^{k}\to\mathcal{K}$,
where $\mathcal{K}$ is our set of colors, by assigning each $k$-tuple a color
based on its isomorphism type. That is, two $k$-tuples $(v_{1},\ldots,v_{k})$
and $(u_{1},\ldots,u_{k})$ receive the same color under $\chi_{0}$ if and only
if the map $v_{i}\mapsto u_{i}$ (for all $i\in[k]$) is an isomorphism of the
induced subgraphs $G[\\{v_{1},\ldots,v_{k}\\}]$ and
$G[\\{u_{1},\ldots,u_{k}\\}]$ and for all $i,j$, $v_{i}=v_{j}\Leftrightarrow
u_{i}=u_{j}$.

For $r\geq 0$, the coloring computed at the $r$th iteration of
Weisfeiler–Leman is refined as follows. For a $k$-tuple
$\overline{v}=(v_{1},\ldots,v_{k})$ and a vertex $x\in V(G)$, define

$\overline{v}(v_{i}/x)=(v_{1},\ldots,v_{i-1},x,v_{i+1},\ldots,v_{k}).$

The coloring computed at the $(r+1)$st iteration, denoted $\chi_{r+1}$, stores
the color of the given $k$-tuple $\overline{v}$ at the $r$th iteration, as
well as the colors under $\chi_{r}$ of the $k$-tuples obtained by substituting
a single vertex in $\overline{v}$ for another vertex $x$. We examine this
multiset of colors over all such vertices $x$. This is formalized as follows:

$\displaystyle\chi_{r+1}(\overline{v})=$
$\displaystyle(\chi_{r}(\overline{v}),\\{\\!\\!\\{(\chi_{r}(\overline{v}(v_{1}/x)),\ldots,\chi_{r}(\overline{v}(v_{k}/x))\bigr{|}x\in
V(G)\\}\\!\\!\\}),$

where $\\{\\!\\!\\{\cdot\\}\\!\\!\\}$ denotes a multiset. Note that the
coloring $\chi_{r}$ computed at iteration $r$ induces a partition of
$V(G)^{k}$ into color classes. The Weisfeiler–Leman algorithm terminates when
this partition is not refined, that is, when the partition induced by
$\chi_{r+1}$ is identical to that induced by $\chi_{r}$. The final coloring is
referred to as the stable coloring, which we denote $\chi_{\infty}:=\chi_{r}$.

The $1$-dimensional Weisfeiler–Leman algorithm, sometimes referred to as Color
Refinement, works nearly identically. Two vertices of $G$ receive the same
initial color if and only if they have the same degree. For the refinement
step, we have that:

$\chi_{r+1}(u)=(\chi_{r}(u),\\{\\!\\!\\{\chi_{r}(v):v\in N(u)\\}\\!\\!\\}).$

We have that $1$-WL terminates when the partition on the vertices is not
refined.

As we are interested in both the Weisfeiler–Leman dimension and the number of
rounds, we will use the following notation.

######  Definition 2.1.

Let $k\geq 1$ and $r\geq 1$ be integers. The $(k,r)$-WL algorithm is obtained
by running $k$-WL for $r$ rounds. Here, the initial coloring counts as the
first round.

Let $S$ be a sequence of vertices. The individualize-and-refine paradigm works
first by assigning each vertex in $S$ a unique color. We then run $(k,r)$-WL
on this colored graph. We denote the coloring computed by $(k,r)$-WL after
individualizing $S$ as $\chi_{k,r}^{S}$.

######  Remark 2.2.

Grohe & Verbitsky [GV06] previously showed that for fixed $k$, the classical
$k$-dimensional Weisfeiler–Leman algorithm for graphs can be effectively
parallelized. Precisely, each iteration (including the initial coloring) can
be implemented using a logspace uniform $\textsf{TC}^{0}$ circuit. In the case
of the count-free $k$-WL algorithm, each round can be implemented using a
logspace uniform $\textsf{AC}^{0}$ circuit.

###  2.2 Pebbling Game

We recall the bijective pebble game introduced by [Hel89, Hel96] for WL on
graphs. This game is often used to show that two graphs $X$ and $Y$ cannot be
distinguished by $k$-WL. The game is an Ehrenfeucht–Fraïssé game (c.f.,
[EFT94, Lib04]), with two players: Spoiler and Duplicator. We begin with $k+1$
pairs of pebbles. Prior to the start of the game, each pebble pair
$(p_{i},p_{i}^{\prime})$ is initially placed either beside the graphs or on a
given pair of vertices $v_{i}\mapsto v_{i}^{\prime}$ (where $v_{i}\in
V(X),v_{i}^{\prime}\in V(Y)$). We refer to this initial configuration for $X$
as $\overline{v}$, and this initial configuration for $Y$ as
$\overline{v^{\prime}}$. Each round $r$ proceeds as follows.

  1. 1.

Spoiler picks up a pair of pebbles $(p_{i},p_{i}^{\prime})$.

  2. 2.

We check the winning condition, which will be formalized later.

  3. 3.

Duplicator chooses a bijection $f_{r}:V(X)\to V(Y)$ (we emphasize that the
bijection chosen depends on the round- and, implicitly, the pebbling
configuration at the start of said round).

  4. 4.

Spoiler places $p_{i}$ on some vertex $v\in V(X)$. Then $p_{i}^{\prime}$ is
placed on $f(v)$.

Let $v_{1},\ldots,v_{m}$ be the vertices of $X$ pebbled at the end of step 1
at round $r$ of the game, and let $v_{1}^{\prime},\ldots,v_{m}^{\prime}$ be
the corresponding pebbled vertices of $Y$. Spoiler wins precisely if the map
$v_{\ell}\mapsto v_{\ell}^{\prime}$ does not extend to an isomorphism of the
induced subgraphs $X[\\{v_{1},\ldots,v_{m}\\}]$ and
$Y[\\{v_{1}^{\prime},\ldots,v_{m}^{\prime}\\}]$. Duplicator wins otherwise.
Spoiler wins, by definition, at round $0$ if $X$ and $Y$ do not have the same
number of vertices. We note that $\overline{v}$ and $\overline{v^{\prime}}$
are not distinguished by the first $r$ rounds of $k$-WL if and only if
Duplicator wins the first $r$ rounds of the $(k+1)$-pebble game [Hel89, Hel96,
CFI92].

######  Remark 2.3.

In our work, we explicitly control for both pebbles and rounds. In our theorem
statements, we state explicitly the number of pebbles on the board. So if
Spoiler can win with $k$ pebbles on the board, then we are playing in the
$(k+1)$-pebble game. Note that $k$-WL corresponds to $k$-pebbles on the board.

###  2.3 Logics

We recall key notions of first-order logic. We have a countable set of
variables $\\{x_{1},x_{2},\ldots\\}$. Formulas are defined inductively. For
the basis, we have that $x_{i}=x_{j}$ is a formula for all pairs of variables.
Now if $\varphi$ is a formula, then so are the following:
$\varphi\land\varphi,\varphi\vee\varphi,\neg{\varphi},\exists{x_{i}}\,\varphi,$
and $\forall{x_{i}}\,\varphi$. In order to define logics on graphs, we add a
relation $E(x,y)$, where $E(x,y)=1$ if and only if $\\{x,y\\}$ is an edge of
our graph, and $0$ otherwise. In keeping with the conventions of [CFI92], we
refer to the first-order logic with relation $E$ as $\mathcal{L}$ and its
$k$-variable fragment as $\mathcal{L}_{k}$. We refer to the logic
$\mathcal{C}$ as the logic obtained by adding counting quantifiers
$\exists^{\geq n}x\,\varphi$ (there exist at least $n$ elements $x$ that
satisfy $\varphi$) and $\exists{!n}\,x\,\varphi$ (there exist exactly $n$
elements $x$ that satisfy $\varphi$) as $\mathcal{C}$ and its $k$-variable
fragment as $\mathcal{C}_{k}$.

The quantifier depth of a formula $\varphi$ (belonging to either $\mathcal{L}$
or $\mathcal{C}$) is the depth of its quantifier nesting. We denote the
quantifier depth of $\varphi$ as $\text{qd}(\varphi)$ This is defined
inductively as follows.

  * •

If $\varphi$ is atomic, then $\text{qd}(\varphi)=0$.

  * •

$\text{qd}(\neg\varphi)=\text{qd}(\varphi)$.

  * •

$\text{qd}(\varphi_{1}\vee\varphi_{2})=\text{qd}(\varphi_{1}\land\varphi_{2})=\max\\{\text{qd}(\varphi_{1}),\text{qd}(\varphi_{2})\\}$.

  * •

$\text{qd}(Qx\,\varphi)=\text{qd}(\varphi)+1$, where $Q$ is a quantifier in
the logic.

We denote the fragment of $\mathcal{L}_{k}$ (respectively, $\mathcal{C}_{k}$)
where the formulas have quantifier depth at most $r$ as $\mathcal{L}_{k,r}$
(respectively, $\mathcal{C}_{k,r}$). Let $\overline{v}\in
V(X)^{k},\overline{v^{\prime}}\in V(Y)^{k}$. We note that
$\overline{v},\overline{v^{\prime}}$ are distinguished by $(k,r)$-WL if and
only if there exists a formula $\varphi\in\mathcal{C}_{k+1,r}$ such that
$(X,\overline{v})\models\varphi$ and
$(Y,\overline{v^{\prime}})\not\models\varphi$ [IL90, CFI92].

##  3 Weisfeiler–Leman for Graphs of Bounded Rank Width

###  3.1 Preliminaries

Rank Width. Oum & Seymour [iOS06] introduced the rank width parameter to
measure the width of a certain hierarchical decomposition of graphs. The goal
is to intuitively split the vertices of a graph along cuts of low complexity
in a hierarchical fashion. Here, the complexity is the $\mathbb{F}_{2}$-rank
of the matrix capturing the adjacencies crossing the cut.

Precisely, let $G$ be a graph, and let $X,Y\subseteq V(G)$. Define
$M(X,Y)\in\mathbb{F}_{2}^{X\times Y}$ to be the matrix where $(M(X,Y))_{uv}=1$
if and only if $uv\in E(G)$. That is, $M(X,Y)$ is the submatrix of the
adjacency matrix whose rows are indexed by $X$ and whose columns are indexed
by $Y$. Denote
$\rho(X):=\operatorname{rk}_{\mathbb{F}_{2}}(M(X,\overline{X}))$.

A rank decomposition of $G$ is a tuple $(T,\gamma)$, where $T$ is a binary
rooted tree and $\gamma:V(T)\to 2^{V(G)}$ satisfying the following:

  * •

For the root $r$ of $T$, $\gamma(r)=V(G)$,

  * •

For an internal node $t\in V(T)$, denote the children of $t$ as $s_{1},s_{2}$.
For every internal node $t$, we have that
$\gamma(t)=\gamma(s_{1})\cup\gamma(s_{2})$, and
$\gamma(s_{1})\cap\gamma(s_{2})=\emptyset$.

  * •

For any leaf $t\in V(T)$, $|\gamma(t)|=1$.

######  Remark 3.1.

Let $L(T)$ be the set of leaves of $T$. Instead of providing $\gamma$, we can
equivalently define a bijection $f:V(G)\to L(T)$. By the second condition of a
rank width decomposition, $f$ completely determines $\gamma$.

The width of a rank decomposition $(T,\gamma)$ is:

$\text{wd}(T,\gamma):=\max\\{\rho_{G}(\gamma(t)):t\in V(T)\\}.$

The rank width of a graph $G$ is:

$\operatorname{rw}(G):=\min\\{\text{wd}(T,\gamma):(T,\gamma)\text{ is a rank
decomposition of }G\\}.$

The parameter rank width is closely related to the parameter clique width,
introduced by Courcelle & Olariu [CO00]. Oum & Seymour [iOS06] showed that:

$\operatorname{rw}(G)\leq\text{cw}(G)\leq 2^{\operatorname{rw}(G)+1}-1.$

Denote $\text{tw}(G)$ to be the treewidth of $G$. Oum [Oum08] showed that
$\operatorname{rw}(G)\leq\text{tw}(G)+1$. Note that $\text{tw}(G)$ cannot be
bounded in terms of $\operatorname{rw}(G)$; for instance, the complete graph
$K_{n}$ has $\operatorname{rw}(K_{n})=1$ but $\text{tw}(K_{n})=n-1$.

Connectivity Lemma. We establish a helper lemma, which effectively states that
Duplicator must respect connected components of pebbled vertices.

######  Lemma 3.2.

Let $G,H$ be graphs. Suppose that $(u,v)\mapsto(u^{\prime},v^{\prime})$ have
been pebbled. Furthermore, suppose that $u,v$ belong to the same connected
component of $G$, while $u^{\prime},v^{\prime}$ belong to different connected
components of $H$. Then Spoiler can win using $1$ additional pebble and
$O(\log n)$ rounds.

###### Proof.

Let $P$ be a shortest $u-v$ path in $G$. Spoiler begins by pebbling a midpoint
$w$ of $P$. Let $w^{\prime}$ be Duplicator’s response. As
$u^{\prime},v^{\prime}$ belong to different components, we may assume without
loss of generality that $w^{\prime}$ belongs to the component containing
$u^{\prime}$. Let $P_{wv}$ be the $w-v$ path within $P$. At the next round,
Spoiler picks up the pebble on $u$ and iterates on the above argument using
$P_{wv}$. This argument only occurs finitely many times until we hit a base
case, where $wv$ is an edge of $G$, while $w^{\prime}v^{\prime}$ is not an
edge of $H$.

At each round, we are cutting the size of the path in half. Thus, at most
$\log_{2}(n)+1$ rounds are required. Observe that only one additional pebble
was used. The result now follows. ∎

###  3.2 Split Pairs and Flip Functions

In designing a pebbling strategy for graphs of bounded rank width, Grohe &
Neuen [GN23] sought to pebble a set of vertices $X\subseteq V(G)$ such that
$\rho(X)\leq k$ and pebbling $X$ partitions the remaining vertices into sets
$C_{1},\ldots,C_{\ell}$ that can be treated independently. Furthermore, we
want for each $i\in[\ell]$ that either $C_{i}\subseteq X$ or
$C_{i}\subseteq\overline{X}$. As there can be many edges between $X$ and
$\overline{X}$, this is hard to accomplish in general. To this end, Grohe &
Neuen [GN23] utilized split pairs and flip functions, which we will recall
shortly.

Let $G$ be a graph, and let $X\subseteq V(G)$. For $v,w\in X$, define the
equivalence relation $v\approx_{X}w$ precisely if
$N(v)\cap\overline{X}=N(w)\cap\overline{X}$. For $v\in X$, define
$\text{vec}_{X}(v):=(a_{vw})_{w\in\overline{X}}\in\mathbb{F}_{2}^{\overline{X}}$
where $a_{vw}=1$ if and only if $vw\in E(G)$. Observe that $v\approx_{X}w$ if
and only if $\text{vec}_{X}(v)=\text{vec}_{X}(w)$. Now for $S\subseteq X$,
define $\text{vec}_{X}(S):=\\{\text{vec}_{X}(v):v\in S\\}$.

######  Definition 3.3.

Let $G$ be a graph, and let $X\subseteq V(G)$. A pair $(A,B)$ is a split pair
for $X$ if the following hold:

  1. (a)

$A\subseteq X$ and $B\subseteq\overline{X}$,

  2. (b)

$\text{vec}_{X}(A)$ forms an $\mathbb{F}_{2}$-linear basis for
$\langle\text{vec}_{X}(X)\rangle$, and

  3. (c)

$\text{vec}_{\overline{X}}(B)$ forms am $\mathbb{F}_{2}$-linear basis for
$\langle\text{vec}_{\overline{X}}(\overline{X})\rangle$.

Observe that $|A|=\rho_{G}(X)=\rho_{G}(\overline{X})=|B|$. Now if $(A,B)$ is a
split pair for $X$, then $(B,A)$ is a split pair for $\overline{X}$. We define
$(\emptyset,\emptyset)$ to be a split pair for $X=V(G)$. An ordered split pair
for $X$ $((a_{1},\ldots,a_{k}),(b_{1},\ldots,b_{k}))$ is a pair such that
$(\\{a_{1},\ldots,a_{k}\\},\\{b_{1},\ldots,b_{k}\\})$ is a split pair for $X$.

######  Lemma 3.4 ([GN23, Lemma 3.3]).

Let $G$ be a graph, and let $X\subseteq V(G)$. Let $(A,B)$ be a split pair for
$X$. If $v,w\in X$ satisfy $N(v)\cap B=N(w)\cap B$, then $v\approx_{X}w$.
Similarly, if $v^{\prime},w^{\prime}\in\overline{X}$ satisfy
$N(v^{\prime})\cap A=N(w^{\prime})\cap A$, then
$v^{\prime}\approx_{\overline{X}}w^{\prime}$.

######  Remark 3.5.

Suppose we individualize a vertex $v$. Let $u\in N(v)$ and $w\not\in N(v)$.
After two rounds of Color Refinement (the initial coloring and a single
refinement step), we have that $\chi_{1,2}(u)\neq\chi_{1,2}(w)$. Using this
observation, we obtain the following.

######  Corollary 3.6 (Compare rounds c.f. [GN23, Corollary 3.4]).

Let $G$ be a graph, and let $X\subseteq V(G)$. Let
$(\overline{a},\overline{b})$ be an ordered split pair for $X$. Let $u,w\in X$
such that
$\chi_{1,2}(u)^{(\overline{a},\overline{b})}=\chi_{1,2}(w)^{(\overline{a},\overline{b})}$.
Then $u\approx_{X}w$. Similarly, for every
$u^{\prime},w^{\prime}\in\overline{X}$ satisfying
$\chi_{1,2}(u^{\prime})^{(\overline{a},\overline{b})}=\chi_{1,2}(w^{\prime})^{(\overline{a},\overline{b})}$,
we have that $u^{\prime}\approx_{\overline{X}}w^{\prime}$.

The goal now is to use a split pair to partition the graph, so that each part
can be handled independently. We argue that individualizing a split pair and
applying $2$ rounds of Color Refinement suffice to yield such a partition. We
follow the strategy of Grohe & Neuen [GN23] in using a flip function.

######  Definition 3.7 ([GN23, Definition 3.5]).

Let $G(V,E,\chi)$ be a vertex-colored graph, with $\chi:V\to\mathcal{C}$ our
coloring. A flip function for $G$ is a function
$f:\mathcal{C}\times\mathcal{C}\to\\{0,1\\}$ such that
$f(c,c^{\prime})=f(c^{\prime},c)$ for all $c,c^{\prime}\in\mathcal{C}$.

For a colored graph $G(V,E,\chi)$ and a flip function $f$, define the flipped
graph $G^{f}(V,E^{f},\chi)$ where:

$\displaystyle E^{f}$ $\displaystyle=\\{vw:vw\in E(G)\text{ and
}f(\chi(v),\chi(w))=0\\}$ $\displaystyle\cup\\{vw:v\neq w,vw\not\in
E(G),\text{ and }f(\chi(v),\chi(w))=1\\}.$

Denote $\text{Comp}(G,f)\subseteq 2^{V(G)}$ be the set of vertex sets of the
connected components of $G^{f}$. Observe that $\text{Comp}(G,f)$ forms a
partition of $V(G)$.

######  Lemma 3.8 (Compare rounds c.f. [GN23, Lemma 3.6]).

Let $G(V,E,\chi)$ be a colored graph, and let $X\subseteq V(G)$. Let
$(\overline{a},\overline{b})$ be a split pair for $X$. Let $k\geq 1,r\geq 2$,
and $G^{\prime}:=G(V,E,\chi_{k,r}^{(\overline{a},\overline{b}),G})$. There
exists a flip function $f$ for $G^{\prime}$ such that for every
$C\in\text{Comp}(G^{\prime},f)$, we have that either $C\subseteq X$ or
$C\subseteq\overline{X}$.

###### Proof (Sketch)..

In the proof of [GN23, Lemma 3.6], Grohe & Neuen rely solely on the fact that
for any vertex $v$, the counting $(1,\infty)$-WL can detect
$N(v)\cap(\overline{a}\cup\overline{b})$ (where here, we abuse notation to
refer to $(\overline{a}\cup\overline{b})$ as the set of vertices in
$(\overline{a},\overline{b})$). As we are dealing with graphs of rank width
$k$, $(\overline{a},\overline{b})$ consists of $O(k)$ vertices. So the
counting $(1,2)$-WL can detect $N(v)\cap(\overline{a}\cup\overline{b})$. Thus,
using $(1,2)$-WL in place of the counting $(1,\infty)$-WL, the proof of [GN23,
Lemma 3.6] holds, mutatis mutandis. ∎

Grohe & Neuen [GN23] previously showed that the flip function preserves
isomorphism. Precisely, they established the following.

######  Lemma 3.9 ([GN23, Lemma 3.9]).

Let $G,G^{\prime}$ be two colored graphs, and let $f$ be a flip function for
$G,G^{\prime}$. Let $\varphi:V(G)\to V(G^{\prime})$ be a bijection. We have
that $\varphi\in\text{Iso}(G,G^{\prime})$ if and only if
$\varphi\in\text{Iso}(G^{f},(G^{\prime})^{f})$.

Grohe & Neuen [GN23, Lemma 3.10] also showed that the flip function respects
the stable-coloring of Weisfeiler–Leman. While the statement of [GN23, Lemma
3.10] did not control for rounds, the result holds even when considering
rounds.

######  Lemma 3.10 ([GN23, Lemma 3.10]).

Let $G,G^{\prime}$ be two colored graphs, and let $f$ be a flip function for
$G,G^{\prime}$. We have that $(k,r)$-WL distinguishes $G,G^{\prime}$ if and
only if $(k,r)$-WL distinguishes $G^{f},(G^{\prime})^{f}$.

###### Proof.

Let $\overline{v},\overline{w}$ be configurations in the $(k+1)$-pebble game.
We have that the map $v_{i}\mapsto w_{i}$ is a marked isomorphism of the
induced subgraphs $G[\overline{v}]$ and $G^{\prime}[\overline{w}]$ if and only
if this map is an isomorphism of the induced subgraphs $G^{f}[\overline{v}]$
and $(G^{\prime})^{f}[\overline{w}]$. ∎

######  Corollary 3.11 (Compare rounds c.f. [GN23, Corollary 3.12]).

Let $G(V,E,\chi),G^{\prime}(V^{\prime},E^{\prime},\chi^{\prime})$ be vertex-
colored graphs, and let $f$ be a flip function for $G,G^{\prime}$. Let
$\overline{v}\in V^{k},\overline{v^{\prime}}\in(V^{\prime})^{k}$. Let $C$ be a
connected component of $G^{f}$ such that $\chi(u)\neq\chi(w)$ for all $u\in C$
and all $w\in V\setminus C$. Let $C^{\prime}$ be a connected component such
that $\chi^{\prime}(u^{\prime})\neq\chi^{\prime}(w^{\prime})$ for all
$u^{\prime}\in C^{\prime}$ and $w^{\prime}\in V^{\prime}\setminus C^{\prime}$.
Let $r\geq 1$. Suppose that:

$(G[C],\chi_{1,r}^{\overline{v},G})\not\cong(G^{\prime}[C^{\prime}],\chi_{1,r}^{\overline{v^{\prime}},G^{\prime}}).$

Let $\overline{w}:=C\cap\overline{v}$ and
$\overline{w^{\prime}}:=C^{\prime}\cap\overline{v^{\prime}}$. Then either:

$(G[C],\chi_{1,r}^{\overline{w},G})\not\cong(G[C^{\prime}],\chi_{1,r}^{\overline{w^{\prime}},G^{\prime}}),$

or $r$ rounds of Color Refinement distinguishes $(G,\chi^{\overline{v}})$ from
$(G^{\prime},(\chi^{\prime})^{\overline{v^{\prime}}})$.

###### Proof.

The proof is by contrapositive. Let $I=\\{i\in[k]:v_{i}\in C\\}$, and let
$I^{\prime}=\\{i\in[k]:v_{i}^{\prime}\in C^{\prime}\\}$. Suppose that
$(1,r)$-WL fails to distinguish $(G,\chi^{\overline{v}})$ and
$(G^{\prime},(\chi^{\prime})^{\overline{v^{\prime}}})$. Them by Lemma 3.9,
$(1,r)$-WL fails to distinguish $(G^{f},\chi^{\overline{v}})$ and
$((G^{\prime})^{f},(\chi^{\prime})^{\overline{v^{\prime}}})$. So we have that
$I=I^{\prime}$. Now suppose that:

$(G[C],\chi_{1,r}^{\overline{w},G})\cong(G[C^{\prime}],\chi_{1,r}^{\overline{w^{\prime}},G^{\prime}}).$

As $I=I^{\prime}$, it follows that:

$(G[C],\chi_{1,r}^{\overline{v},G})\cong(G[C^{\prime}],\chi_{1,r}^{\overline{v^{\prime}},G^{\prime}}).$

As $1$-WL only takes into account the neighbors of a given vertex in the
refinement step, we have by induction that for each $i\leq r$:

$(G[C],\chi_{1,i}^{\overline{v},G})\cong(G[C^{\prime}],\chi_{1,i}^{\overline{v^{\prime}},G^{\prime}}).$

The result now follows. ∎

###  3.3 WL for Graphs of Bounded Rank Width

Our goal in this section is to establish the following.

######  Theorem 3.12.

Let $G$ be a graph of rank width $k$, and let $H$ be an arbitrary graph such
that $G\not\cong H$. We have that the $(6k+3,O(\log n))$-WL algorithm will
distinguish $G$ from $H$.

######  Definition 3.13 ([GN23, Definition 4.1]).

Let $G$ be a graph, and let $X,X_{1},X_{2}\subseteq V(G)$ such that
$X=X_{1}\sqcup X_{2}$. Let $(A,B)$ be a split pair for $X$, and let
$(A_{i},B_{i})$ ($i=1,2)$ be a split pair for $X_{i}$. We say that
$(A_{i},B_{i})$ are nice with respect to $(A,B)$ if the following conditions
hold:

  1. (a)

$A\cap X_{i}\subseteq A_{i}$ for each $i\in\\{1,2\\}$, and

  2. (b)

$B_{2}\cap X_{1}\subseteq A_{1}$ and similarly $B_{1}\cap X_{2}\subseteq
A_{2}$.

A triple of ordered split pairs is nice if the underlying triple of unordered
split pairs is nice.

######  Lemma 3.14 ([GN23, Lemma 4.2]).

Let $G$ be a graph, and let $X,X_{1},X_{2}\subseteq V(G)$ such that
$X=X_{1}\sqcup X_{2}$. Let $(A,B)$ be a split pair for $X$. There exist nice
split pairs $(A_{i},B_{i})$ for $X_{i}$ ($i=1,2$) such that additionally
$B_{i}\cap\overline{X_{i}}\subseteq B$.

######  Definition 3.15.

Let $G$ be a graph. A component partition of $G$ is a partition $\mathcal{P}$
of $V(G)$ such that every connected component appears in exactly one block of
$\mathcal{P}$. That is, for every connected component $C$ of $G$, there exists
a $P\in\mathcal{P}$ such that $C\subseteq P$.

######  Lemma 3.16 ([GN23, Observation 4.3]).

Let $G,H$ be two non-isomorphic graphs, and let $\mathcal{P},\mathcal{Q}$ be
component partitions of $G,H$ respectively. Let $\sigma:V(G)\to V(H)$ be a
bijection. There exists a vertex $v$ such that $G[P]\not\cong H[Q]$, where
$P\in\mathcal{P}$ is the unique set containing $v$ and $Q\in\mathcal{Q}$ is
the unique set containing $\sigma(v)$.

We now prove Theorem 3.12.

###### Proof of Theorem 3.12.

We follow the strategy of [GN23, Theorem 4.4]. Let $G(V,E,\chi_{G})$ be a
colored graph of rank width $\leq k$, and let $H$ be an arbitrary graph such
that $G\not\cong H$. By [CK07, Theorem 5], $G$ admits a rank decomposition
$(T,\gamma)$ of width at most $2k$ where $T$ has height at most
$3\cdot(\log(n)+1)$.

We will show that Spoiler has a winning strategy in the $6k+3$ pebble game in
$O(\log n)$ rounds. In a similar manner as in the proof of [GN23, Theorem
4.4], we will first argue that $12k+5$ pebbles suffice, and then show how to
improve the bound to use only $6k+3$ pebbles.

Spoiler’s strategy is to play along the rank decomposition $(T,\gamma)$
starting from the root. As Spoiler proceeds down the tree, the non-isomorphism
is confined to increasingly smaller parts of $G$ and $H$. At a node $t\in
V(T)$, Spoiler pebbles a split pair $(\overline{a},\overline{b})$ of
$X=\gamma(t)$. Now to confine the non-isomorphism, Spoiler identifies, after
individualizing the split pair and performing two steps of Color Refinement-
the initial coloring and a single refinement step, a pair of non-isomorphic
components $C\subseteq X,C^{\prime}\subseteq V(H)$ in the flipped graphs
$G^{f}$ and $H^{f}$. In particular, Spoiler seeks to find such components $C$
and $C^{\prime}$ such that $C$ is increasingly further from the root of $T$.
Once Spoiler reaches a leaf node of $T$, Spoiler can quickly win. Spoiler
places a pebble on a vertex in $C$ and its image in $C^{\prime}$, under
Duplicator’s bijection at the given round.

We note that the two rounds of Color Refinement suffice for WL to detect the
partitioning induced by the flip function (see Lemma 3.8), though it is not
sufficiently powerful to detect the connected components of $G^{f}$ and
$H^{f}$. In the argument below, we will technically consider graphs where the
refinement step uses $(2,O(\log n))$-WL. This ensures that after
individualizing a vertex on a given component $C$, that the vertices of $C$
receive different colors than those of $V(G)\setminus C$. This will eventually
happen, and so in the pebble game characterization, we can continue to descend
along $T$ as if the vertices of $C$ have been distinguished from
$V(G)\setminus C$. This is a key point where our strategy deviates from that
of [GN23, Theorem 4.4].

Suppose that at a given round, we have the pebbled configuration
$((\overline{a},\overline{b},v),(\overline{a^{\prime}},\overline{b^{\prime}},v^{\prime}))$,
where:

  * •

There exists a $t\in T$ such that $(\overline{a},\overline{b})$ is a split
pair for $\gamma(t)$,

  * •

$v\in\gamma(t)$, and let $C$ be the component containing $v$; and

  * •

$v^{\prime}$ belongs to some component $C^{\prime}$ of $H$ such that:

$(G[C],\chi_{2,O(\log
n)}^{(\overline{a},\overline{b},v)})\not\cong(H[C^{\prime}],\chi_{2,O(\log
n)}^{(\overline{a^{\prime}},\overline{b^{\prime}},v)}).$

Observe that this configuration uses at most $4k+1$ pebbles ($2k$ pebbles for
$\overline{a}$, $2k$ pebbles for $\overline{b}$, and a single pebble for $v$).
Now by Lemma 3.8, we may assume that $C\subseteq\gamma(t)$. Grohe & Neuen
[GN23, Theorem 4.4] observed that
$\chi_{\infty}^{\overline{a},\overline{b},v}(u_{1})\neq\chi_{\infty}^{\overline{a},\overline{b},v}(u_{2})$
for all $u_{1}\in C$ and all $u_{2}\in V(G)\setminus C$. However, in order to
obtain the analogous result using $O(\log n)$ rounds, Lemma 3.2 provides that
we need $2$-WL. Note that we will be using WL of dimension $\geq 9$.
Furthermore, $T$ has height $3\cdot(\log(n)+1)$, we will be running
$(6k+3)$-WL for $\geq 3\cdot(\log(n)+1)$ rounds. Thus, we may assume without
loss of generality that Duplicator selects bijections that map $C\mapsto
C^{\prime}$ (setwise).

By definition, if $t\in V(T)$ is the root node, then $\gamma(t)=V(G)$. So the
empty configuration is a split pair for $\gamma(t)$. We now show by induction
on $|\gamma(t)|$ that Spoiler can win from such a position.

Suppose $t$ is a leaf node. Then $|\gamma(t)|=1$. In this case, $C=\\{v\\}$.
If
$(G[C],\chi_{1,2}^{(\overline{a},\overline{b},v)})\not\cong(H[C^{\prime}],\chi_{1,2}^{(\overline{a^{\prime}},\overline{b^{\prime}},v^{\prime})})$,
then either (i) $v$ and $v^{\prime}$ are assigned different colors, or (ii)
$|C^{\prime}|>1$. In either case, Spoiler wins with at most $1$ additional
pebble and $1$ additional round.

For the inductive step, suppose $|\gamma(t)|>1$. Let $t_{1},t_{2}$ be the
children of $t$ in $T$, and let $X_{i}:=\gamma(t_{i})$ ($i=1,2$). By Lemma
3.14, there exist nice split pairs $(\overline{a}_{i},\overline{b}_{i})$ for
$t_{i}$. Spoiler pebbles
$(\overline{a}_{1},\overline{b}_{1},\overline{a}_{2},\overline{b}_{2})$. Let
$(\overline{a^{\prime}_{1}},\overline{b^{\prime}_{1}},\overline{a^{\prime}_{2}},\overline{b^{\prime}_{2}})$
be Duplicator’s response. Let
$\alpha:=(\overline{a},\overline{b},\overline{a}_{1},\overline{b}_{1},\overline{a}_{2},\overline{b}_{2},v)$,
and let
$\alpha^{\prime}:=(\overline{a^{\prime}},\overline{b^{\prime}},\overline{a^{\prime}_{1}},\overline{b^{\prime}_{1}},\overline{a^{\prime}_{2}},\overline{b^{\prime}_{2}},v^{\prime})$.
As Grohe & Neuen [GN23, Theorem 4.1] noted, the intuitive advantage of
pebbling nice split pairs is that we can remove the pebbles from
$\overline{a},\overline{b}$ and $\overline{a}_{3-i},\overline{b}_{3-i}$
without unpebbling some element of $X_{i}$. We will use this later in our
analysis.

Let $f_{i}$ be the flip function with respect to the split pair
$(\overline{a}_{i},\overline{b}_{i})$ for $X_{i}$ obtained via Lemma 3.8. Let
$f:V(G)\to V(H)$ be the bijection that Duplicator selects. We may assume that
$f(C)=C^{\prime}$; otherwise, there exists a vertex $w\in C$ such that
$f(w)\not\in C^{\prime}$. Spoiler places a pebble on $w\mapsto f(w)$. Now by
Lemma 3.2, Spoiler wins using one more pebble and $O(\log n)$ rounds.

Now without loss of generality, suppose $v\in X_{1}$. Let
$S:=\\{C_{1},\ldots,C_{p}\\}$ be the components of $\text{Comp}(G,f_{1})$ that
intersect non-trivially with $C$. Let
$S^{\prime}:=\\{C_{1}^{\prime},\ldots,C_{p}^{\prime}\\}$ be the analogous set
of components in $\text{Comp}(H,f_{1})$ that intersect non-trivially with
$C^{\prime}$. By Lemma 3.9, we have that:

$((G^{f})[C],\chi_{2,O(\log
n)}^{\overline{\alpha}})\not\cong((H^{f})[C^{\prime}],\chi_{2,O(\log
n)}^{\overline{\alpha^{\prime}}}).$

Let $f^{\prime}:V(G)\to V(H)$ be the bijection that Duplicator selects. Now by
Lemma 3.16, there exists some $w\in C$ such that

$((G^{f})[C\cap C_{i}],\chi_{2,O(\log
n)}^{\overline{\alpha}})\not\cong((H^{f})[C^{\prime}\cap
C_{i}^{\prime}],\chi_{2,(O(\log n)}^{\overline{\alpha^{\prime}}}),$

where $i\in[p]$ is the unique index such that $C_{i}$ contains $w$. We label
$C_{i}^{\prime}$ to be the unique component of $S^{\prime}$ containing
$f^{\prime}(w)$. By Lemma 3.9, we have that:

$(G[C\cap C_{i}],\chi_{2,O(\log
n)}^{\overline{\alpha}})\not\cong(H[C^{\prime}\cap
C_{i}^{\prime}],\chi_{2,O(\log n)}^{\overline{\alpha^{\prime}}}).$

By Lemma 3.8, we have that $C_{i}\subseteq X_{1}$ or
$C_{i}\subseteq\overline{X_{1}}$. In particular, $C\cap C_{i}\subseteq X_{1}$
or $C\cap C_{i}\subseteq X_{2}$. We consider the following cases.

  * •

Case 1: Suppose that $C\cap C_{i}\subseteq X_{1}$. As the configuration
$\overline{\alpha}$ has been pebbled, we have by Lemma 3.2 that
$\chi_{2,O(\log n)}^{\overline{\alpha}}((u_{1},u_{1}))\neq\chi_{2,O(\log
n)}^{\overline{\alpha}}((u_{2},u_{2}))$ for all $u_{1}\in C_{i}$ and all
$u_{2}\in V(G)\setminus C_{i}$. It follows that:

$(G[C_{i}],\chi_{2,O(\log
n)}^{\overline{\alpha}})\not\cong(H[C_{i}^{\prime}],\chi_{2,O(\log
n)}^{\overline{\alpha^{\prime}}}).$

If we do not have both $v\in C_{i}$ and $v^{\prime}\in C_{i}^{\prime}$, then
Spoiler pebbles $w\mapsto f^{\prime}(w)$. Define:

$\overline{\alpha}_{1}:=\begin{cases}\overline{\alpha}&:v\in C_{i}\text{ and
}v^{\prime}\in C_{i}^{\prime},\\\
(\overline{\alpha},w)&:\text{otherwise}.\end{cases}$

Define $\overline{\alpha^{\prime}_{1}}$ analogously. Observe that:

$(G[C_{i}],\chi_{2,O(\log
n)}^{\overline{\alpha}_{1}})\not\cong(H[C_{i}^{\prime}],\chi_{2,O(\log
n)}^{\overline{\alpha^{\prime}}_{1}}).$

We again consider the flip function $f_{1}$. We have that $C_{i}$ forms a
connected component in $G^{f_{1}}$, and similarly $C_{i}^{\prime}$ forms a
connected component in $H^{f_{1}}$. Thus, we may remove pebbles from outside
of $C_{i}$ (respectively $C_{i}^{\prime}$) without changing whether
$\chi_{2,O(\log n)}$ distinguishes $G[C_{i}]$ and $H[C_{i}^{\prime}]$. So we
may remove all pebbles
$\overline{a},\overline{b},\overline{a}_{2},\overline{b}_{2}$. If $w\mapsto
f^{\prime}(w)$ was additionally pebbled, we may also remove the pebble pair
$v\mapsto v^{\prime}$. For convenience, we label:

$z=\begin{cases}v&:v\in C_{i}\text{ and }v^{\prime}\in C_{i}^{\prime},\\\
w&:\text{otherwise}.\end{cases}$

Define $z^{\prime}$ analogously. So now we have that:

$(G[C_{i}],\chi_{2,O(\log
n)}^{(\overline{a}_{1},\overline{b}_{1},z)})\not\cong(H[C_{i}^{\prime}],\chi_{2,O(\log
n)}^{(\overline{a^{\prime}_{1}},\overline{b^{\prime}_{1}},z^{\prime})});$

otherwise, by Corollary 3.11, Spoiler can win with $2$ pebbles (reusing
pebbles we have removed) and $O(\log n)$ additional rounds. Thus, we have not
used any additional pebbles in this case. We now apply the inductive
hypothesis to $t_{1}$ to deduce that Spoiler wins from
$((\overline{a}_{1},\overline{b}_{1},z),(\overline{a^{\prime}_{1}},\overline{b^{\prime}_{1}},z^{\prime}))$.

  * •

Case 2: Suppose $C\cap C_{i}\subseteq X_{2}$. As $X_{1}$ is defined with
respect to the flip function $f_{1}$, this case is not symmetric with respect
to Case 1. Define $M:=C\cap C_{i}$ and $M^{\prime}:=C^{\prime}\cap
C_{i}^{\prime}$.

Spoiler begins by pebbling $w\mapsto f^{\prime}(w)$. Now consider the flip
function $f_{2}$. As the configuration $\overline{\alpha}$ has been pebbled
and by Lemma 3.2, we have that $\chi_{2,O(\log
n)}^{\overline{\alpha}}((u_{1},u_{1}))\neq\chi_{2,O(\log
n)}^{\overline{\alpha}}((u_{2},u_{2}))$ for all $u_{1}\in M$ and all $u_{2}\in
V(G)\setminus M$.

Let $f^{\prime\prime}:V(G)\to V(H)$ be the bijection that Duplicator selects
at the next round. As $\overline{\alpha}$ has been pebbled, we may assume that
$f^{\prime\prime}(M)=M^{\prime}$; otherwise, Spoiler pebbles some element of
$M$ that does not map to an element of $M^{\prime}$. Then by Lemma 3.2,
Spoiler wins with $1$ pebble (removing a pebble of $\overline{\alpha}_{1}$)
and $O(\log n)$ additional rounds. Let $\\{D_{1},\ldots,D_{q}\\}$ be the
components of $\text{Comp}(G,f_{2})$ that intersect $M$ non-trivially, and
define $\\{D_{1}^{\prime},\ldots,D_{q}^{\prime}\\}$ to be the components of
$\text{Comp}(H,f_{2})$ that intersect $M^{\prime}$ non-trivially.

By Lemma 3.9 and as $\overline{\alpha},w$ have been pebbled, we have that:

$(G^{f_{2}}[M],\chi_{2,O(\log
n)}^{(\overline{\alpha},w)})\not\cong(H^{f_{2}}[M^{\prime}],\chi_{2,O(\log
n)}^{(\overline{\alpha},w)}).$

By Lemma 3.16, there exists some $z\in M$ such that:

$(G^{f_{2}}[M\cap D_{j}],\chi_{2,O(\log
n)}^{(\overline{\alpha},w)})\not\cong(H^{f_{2}}[M^{\prime}\cap
D_{j}^{\prime}],\chi_{2,O(\log n)}^{(\overline{\alpha},w)}),$

where $j\in[q]$ is the unique component containing $z$. Let $D_{j}^{\prime}$
be the corresponding component containing $f^{\prime\prime}(z)$. It follows
that:

$(G^{f_{2}}[M\cap D_{j}],\chi_{2,O(\log
n)}^{(\overline{\alpha},w,z)})\not\cong(H^{f_{2}}[M^{\prime}\cap
D_{j}^{\prime}],\chi_{2,O(\log
n)}^{(\overline{\alpha},w,f^{\prime\prime}(z))}),$

Applying Lemma 3.9 again, we have that:

$(G[M\cap D_{j}],\chi_{2,O(\log
n)}^{(\overline{\alpha},w,z)})\not\cong(H[M^{\prime}\cap
D_{j}^{\prime}],\chi_{2,O(\log
n)}^{(\overline{\alpha},w,f^{\prime\prime}(z))}).$

Now if $w\in D_{i}$ and $w^{\prime}\in D_{i}^{\prime}$, Spoiler does not place
an additional pebble. Otherwise, Spoiler pebbles $z\mapsto
f^{\prime\prime}(z)$. For convenience, we define:

$x=\begin{cases}w&:w\in D_{j}\text{ and }w^{\prime}\in D_{j}^{\prime}\\\
z&:\text{otherwise.}\end{cases}$

Define $x^{\prime}$ analogously. Now as

$(G[M\cap D_{j}],\chi_{2,O(\log
n)}^{(\overline{\alpha},w,z)})\not\cong(H[M^{\prime}\cap
D_{j}^{\prime}],\chi_{2,O(\log
n)}^{(\overline{\alpha},w,f^{\prime\prime}(z))}),$

we have that:

$(G[M\cap D_{j}],\chi_{2,O(\log
n)}^{(\overline{\alpha},w,x)})\not\cong(H[M^{\prime}\cap
D_{j}^{\prime}],\chi_{2,O(\log n)}^{(\overline{\alpha},w,x)}).$

Now in the flipped graph $G^{f_{2}}$, $D_{i}$ forms a connected component.
Similarly, in $H^{f_{2}}$, $D_{i}^{\prime}$ forms a connected component. So
removing any pebbles from outside of $D_{i}$ (respectively, $D_{i}^{\prime}$)
does not affect whether $\chi_{2,O(\log n)}$ distinguishes $D_{i}$ from
$V(G)\setminus D_{i}$ (respectively, whether $\chi_{2,O(\log n)}$
distinguishes $D_{i}^{\prime}$ from $V(H)\setminus D_{i}^{\prime}$). So we may
remove all pebbles, so that only
$(\overline{a}_{2},\overline{b}_{2},x)\mapsto(\overline{a^{\prime}_{2}},\overline{b^{\prime}_{2}},x^{\prime})$
remain pebbled and still obtain that:

$(G[D_{j}],\chi_{2,O(\log
n)}^{(\overline{a}_{2},\overline{b}_{2}x)})\not\cong(H[D_{j}^{\prime}],\chi_{2,O(\log
n)}^{(\overline{a^{\prime}_{2}},\overline{b^{\prime}_{2}},x^{\prime})}).$

Otherwise, Spoiler wins using $2$ pebbles we have removed and $O(\log n)$
additional rounds. We now apply the inductive hypothesis to $t_{2}$, to deduce
that Spoiler wins from
$((\overline{a}_{2},\overline{b}_{2},z),(\overline{a^{\prime}_{2}},\overline{b^{\prime}_{2}},z^{\prime}))$.

So by induction, Spoiler has a winning strategy. It remains to analyze the
round and pebble complexities. We first claim that only $O(\log n)$ rounds are
necessary. At each node of the host tree, only a constant number of rounds are
necessary unless (i) Duplicator selects a bijection that does not respect
connected components, or (ii) we apply Corollary 3.11. Note that either case
can only happen once. If Duplicator selects a bijection that does not respect
connected components, then by Lemma 3.2, Spoiler wins with $O(\log n)$ rounds.
Thus, as the height of $T$ is $O(\log n)$, only $O(\log n)$ rounds are
necessary.

We will now analyze the number of pebbles, following the same strategy as
Grohe & Neuen [GN23]. We can pebble
$(\overline{a},\overline{b},\overline{a}_{1},\overline{b}_{1},\overline{a}_{2},\overline{b}_{2})$
using $12k$ pebbles, as $(T,\gamma)$ has width at most $2k$. As
$\overline{a}\subseteq\overline{a}_{1}\cup\overline{a}_{2}$, we need not
pebble $\overline{a}$ and so can use only $10k$ pebbles. By Lemma 3.14,
Spoiler can choose nice split pairs $(\overline{a},\overline{b})$ and
$(\overline{a}_{i},\overline{b}_{i})$ such that additionally
$\overline{b}_{i}\cap\overline{X}\subseteq\overline{b}$. So
$\overline{b}_{i}\subseteq\overline{b}\cup\overline{a}_{3-i}$. This brings us
down to $6k$ pebbles.

At most two of $x,v,w$ are pebbled at a given round. By Lemma 3.14, we can
remove pebbles from $b_{2}$ in Case 1 or $b_{1}$ in Case 2. So only one
additional pebble is necessary. Furthermore, if Duplicator selects bijections
that do not respect connected components corresponding to pebbled vertices,
then Duplicator can remove pebbles from $b_{2}$ in Case 1 or $b_{1}$ in Case 2
to win (see Lemma 3.2). So at most $1$ additional pebble is required. Thus,
Spoiler has a winning strategy with $6k+3$ pebbles on the board and $O(\log
n)$ rounds. The result follows. ∎

######  Remark 3.17.

If we use a rank decomposition of width $k$, then we are able to obtain a
slight improvement upon [GN23, Theorem 4.1], using $(3k+3)$-WL (without
controlling for rounds) rather than $(3k+4)$-WL.

######  Corollary 3.18.

The Weisfeiler–Leman dimension of graphs of rank width $k$ is $\leq 3k+3$.

##  4 Conclusion

We showed that the $(6k+3,O(\log n))$-WL algorithm identifies graphs of
bounded rank width. As a consequence, we obtain a $\textsf{TC}^{1}$ upper
bound for isomorphism testing of graphs of bounded rank width. In the process,
we also improved the Weisfeiler–Leman dimension from $3k+4$ [GN23] to $3k+3$,
though it is not known if even $(3k+4)$-WL can identify graphs of bounded rank
width in $O(\log n)$ rounds. We conclude with several open questions.

It would be of interest to close the gap between the $(3k+3)$-WL bound where
the iteration number is unknown and our $(6k+3)$-WL upper bound to obtain
$O(\log n)$ rounds. One possible strategy would be to show that the exists a
rank decomposition of width $k$ where the host tree has height $O(\log n)$.

######  Question 4.1.

Let $G$ be a graph of rank width $k$. Does there exist a rank decomposition
$(T,\gamma)$ of width $k$ such that $T$ has height $O(\log n)$?

Courcelle & Kante [CK07] showed that a rank decomposition of width $2k$ exists
with a host tree of height $3(\log(n)+1)$. Decreasing the width to some $k\leq
c\leq 2k$ at the cost of increasing the height of the host tree by a constant
factor would immediately yield improvements. More generally, in light of the
correspondence between WL and $\textsf{FO}+\textsf{C}$, the width of the rank
decomposition corresponds to the number of variables, and the depth of the
host tree corresponds to the quantifier depth in formulas characterizing these
graphs. Thus, controlling the trade-off between the width of the rank
decomposition and the height of the host tree would directly translate into a
trade-off between the number of variables and the quantifier depth in our
logical formula.

We note that isomorphism testing for graphs of bounded treewidth [ES17] is
L-complete under $\textsf{AC}^{0}$-reductions. As graphs of bounded treewidth
also have bounded rank width, we have that isomorphism testing for graphs of
bounded rank width is L-hard under $\textsf{AC}^{0}$-reductions. We thus ask
the following.

######  Question 4.2.

Is isomorphism testing of graphs of bounded rank width L-complete?

It is natural to ask whether the standard counting Weisfeiler–Leman algorithm
can identify graphs of bounded rank width in $o(\log n)$ rounds. While we lack
good lower bounds for the standard counting WL, there are lower bounds against
the constant-dimensional count-free WL.

######  Lemma 4.3.

The count-free $(O(1),\operatorname{poly}\log\log n)$-WL is unable to identify
graphs of bounded treewidth (and hence, graphs of bounded rank width).

###### Proof.

As isomorphism testing for graphs of bounded treewidth is L-complete under
$\textsf{AC}^{0}$-reductions [ES17], we have that Parity is
$\textsf{AC}^{0}$-reducible to isomorphism testing for graphs of bounded
treewidth. If the count-free $(O(1),\operatorname{poly}\log\log n)$-WL were
able to identify graphs of bounded treewidth, then isomorphism testing for
graphs of bounded treewidth– and hence, Parity– would belong to
$\textsf{FO}(\operatorname{poly}\log\log n)$. However,
$\textsf{FO}(\operatorname{poly}\log\log n)$ cannot compute Parity [Smo87], a
contradiction. ∎

On the other hand, we are not aware as to whether isomorphism testing of trees
can be done using a logspace uniform TC circuit of depth $O(\log\log n)$. An
answer of no would establish a lower bound of $\omega(\log\log n)$ rounds for
the standard counting WL to identify trees, planar graphs, graphs of bounded
tree width, and graphs of bounded rank width.

######  Question 4.4.

Is isomorphism testing of trees decidable using a logspace uniform TC circuit
of depth $O(\log\log n)$?

It was already known that GI parameterized by rank width was in XP [GS15,
GN23]. While our results improve the parallel complexity, they do not improve
the parameterized complexity.

######  Question 4.5.

Does isomorphism testing of graphs parameterized by rank width belong to FPT?

## References

  * [AK06] V. Arvind and Piyush P. Kurur.  Graph isomorphism is in SPP.  Information and Computation, 204(5):835–852, 2006.  doi:10.1016/j.ic.2006.02.002.
  * [Bab16] László Babai.  Graph isomorphism in quasipolynomial time [extended abstract].  In STOC’16—Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, pages 684–697. ACM, New York, 2016.  Preprint of full version at arXiv:1512.03547v2 [cs.DS].  doi:10.1145/2897518.2897542.
  * [BES80] László Babai, Paul Erdös, and Stanley M. Selkow.  Random graph isomorphism.  SIAM Journal on Computing, 9(3):628–635, 1980.  doi:10.1137/0209047.
  * [BH92] Harry Buhrman and Steven Homer.  Superpolynomial circuits, almost sparse oracles and the exponential hierarchy.  In R. K. Shyamasundar, editor, Foundations of Software Technology and Theoretical Computer Science, 12th Conference, New Delhi, India, December 18-20, 1992, Proceedings, volume 652 of Lecture Notes in Computer Science, pages 116–127. Springer, 1992.  doi:10.1007/3-540-56287-7\\_99.
  * [BK79] László Babai and Ludik Kucera.  Canonical labelling of graphs in linear average time.  In 20th Annual Symposium on Foundations of Computer Science (SFCS 1979), pages 39–46, 1979.  doi:10.1109/SFCS.1979.8.
  * [BKL83] L. Babai, W. M. Kantor, and E. M. Luks.  Computational complexity and the classification of finite simple groups.  In 24th Annual Symposium on Foundations of Computer Science (sfcs 1983), pages 162–171, 1983.  doi:10.1109/SFCS.1983.10.
  * [BL83] László Babai and Eugene M. Luks.  Canonical labeling of graphs.  In Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing, STOC ’83, page 171–183, New York, NY, USA, 1983. Association for Computing Machinery.  doi:10.1145/800061.808746.
  * [Bol82] Béla Bollobás.  Distinguishing vertices of random graphs.  In Béla Bollobás, editor, Graph Theory, volume 62 of North-Holland Mathematics Studies, pages 33–49. North-Holland, 1982.  doi:10.1016/S0304-0208(08)73545-X.
  * [CFI92] Jin-Yi Cai, Martin Fürer, and Neil Immerman.  An optimal lower bound on the number of variables for graph identification.  Combinatorica, 12(4):389–410, 1992.  Originally appeared in SFCS ’89.  doi:10.1007/BF01305232.
  * [CK07] Bruno Courcelle and Mamadou Kanté.  Graph operations characterizing rank-width and balanced graph expressions.  pages 66–75, 06 2007.  doi:10.1007/978-3-540-74839-7_7.
  * [CO00] Bruno Courcelle and Stephan Olariu.  Upper bounds to the clique width of graphs.  Discrete Applied Mathematics, 101(1):77–114, 2000.  doi:10.1016/S0166-218X(99)00184-5.
  * [DLN+09] Samir Datta, Nutan Limaye, Prajakta Nimbhorkar, Thomas Thierauf, and Fabian Wagner.  Planar graph isomorphism is in log-space.  In 2009 24th Annual IEEE Conference on Computational Complexity, pages 203–214, 2009.  doi:10.1109/CCC.2009.16.
  * [DTW12] Bireswar Das, Jacobo Torán, and Fabian Wagner.  Restricted space algorithms for isomorphism on bounded treewidth graphs.  Information and Computation, 217:71–83, 2012.  doi:10.1016/j.ic.2012.05.003.
  * [Edm65] Jack Edmonds.  Paths, trees, and flowers.  Canadian Journal of Mathematics, 17:449–467, 1965.  doi:10.4153/CJM-1965-045-4.
  * [EFT94] Heinz-Dieter Ebbinghaus, J. Flum, and W. Thomas.  Mathematical Logic.  Springer, 2 edition, 1994.  doi:10.1007/978-1-4757-2355-7.
  * [EK14] Michael Elberfeld and Ken-ichi Kawarabayashi.  Embedding and canonizing graphs of bounded genus in logspace.  In David B. Shmoys, editor, Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 383–392. ACM, 2014.  doi:10.1145/2591796.2591865.
  * [ES17] Michael Elberfeld and Pascal Schweitzer.  Canonizing graphs of bounded tree width in logspace.  ACM Trans. Comput. Theory, 9(3), oct 2017.  doi:10.1145/3132720.
  * [FGS19] Vyacheslav Futorny, Joshua A. Grochow, and Vladimir V. Sergeichuk.  Wildness for tensors.  Lin. Alg. Appl., 566:212–244, 2019.  Preprint arXiv:1810.09219 [math.RT].  doi:10.1016/j.laa.2018.12.022.
  * [FSS83] Martin Fürer, Walter Schnyder, and Ernst Specker.  Normal forms for trivalent graphs and graphs of bounded valence.  In Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing, STOC ’83, page 161–170, New York, NY, USA, 1983. Association for Computing Machinery.  doi:10.1145/800061.808745.
  * [GK19] Martin Grohe and Sandra Kiefer.  A Linear Upper Bound on the Weisfeiler-Leman Dimension of Graphs of Bounded Genus.  In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), volume 132 of Leibniz International Proceedings in Informatics (LIPIcs), pages 117:1–117:15, Dagstuhl, Germany, 2019. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.  doi:10.4230/LIPIcs.ICALP.2019.117.
  * [GK21] Martin Grohe and Sandra Kiefer.  Logarithmic Weisfeiler-Leman Identifies All Planar Graphs.  In Nikhil Bansal, Emanuela Merelli, and James Worrell, editors, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), volume 198 of Leibniz International Proceedings in Informatics (LIPIcs), pages 134:1–134:20, Dagstuhl, Germany, 2021. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.  doi:10.4230/LIPIcs.ICALP.2021.134.
  * [GM15] Martin Grohe and Dániel Marx.  Structure theorem and isomorphism test for graphs with excluded topological subgraphs.  SIAM Journal on Computing, 44(1):114–159, 2015.  doi:10.1137/120892234.
  * [GN23] Martin Grohe and Daniel Neuen.  Canonisation and definability for graphs of bounded rank width.  ACM Trans. Comput. Log., 24(1):6:1–6:31, 2023.  doi:10.1145/3568025.
  * [GNS0] Martin Grohe, Daniel Neuen, and Pascal Schweitzer.  A faster isomorphism test for graphs of small degree.  SIAM Journal on Computing, 0(0):FOCS18–1–FOCS18–36, 0.  doi:10.1137/19M1245293.
  * [GNSW20] Martin Grohe, Daniel Neuen, Pascal Schweitzer, and Daniel Wiebking.  An improved isomorphism test for bounded-tree-width graphs.  ACM Trans. Algorithms, 16(3), 06 2020.  doi:10.1145/3382082.
  * [GQ19] Joshua A. Grochow and Youming Qiao.  Isomorphism problems for tensors, groups, and cubic forms: completeness and reductions.  arXiv:1907.00309 [cs.CC], 2019.  doi:10.48550/ARXIV.1907.00309.
  * [Gro00] Martin Grohe.  Isomorphism testing for embeddable graphs through definability.  In Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, STOC ’00, page 63–72, New York, NY, USA, 2000. Association for Computing Machinery.  doi:10.1145/335305.335313.
  * [Gro12] Martin Grohe.  Fixed-point definability and polynomial time on graphs with excluded minors.  J. ACM, 59(5), nov 2012.  doi:10.1145/2371656.2371662.
  * [Gro17] Martin Grohe.  Descriptive complexity, canonisation, and definable graph structure theory, volume 47 of Lecture Notes in Logic.  Association for Symbolic Logic, Ithaca, NY; Cambridge University Press, Cambridge, 2017.  doi:10.1017/9781139028868.
  * [GS15] Martin Grohe and Pascal Schweitzer.  Isomorphism testing for graphs of bounded rank width.  In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 1010–1029, 2015.  doi:10.1109/FOCS.2015.66.
  * [GV06] Martin Grohe and Oleg Verbitsky.  Testing graph isomorphism in parallel by playing a game.  In Michele Bugliesi, Bart Preneel, Vladimiro Sassone, and Ingo Wegener, editors, Automata, Languages and Programming, 33rd International Colloquium, ICALP 2006, Venice, Italy, July 10-14, 2006, Proceedings, Part I, volume 4051 of Lecture Notes in Computer Science, pages 3–14. Springer, 2006.  doi:10.1007/11786986_2.
  * [Hel89] Lauri Hella.  Definability hierarchies of generalized quantifiers.  Annals of Pure and Applied Logic, 43(3):235 – 271, 1989.  doi:10.1016/0168-0072(89)90070-5.
  * [Hel96] Lauri Hella.  Logical hierarchies in PTIME.  Information and Computation, 129(1):1–19, 1996.  doi:10.1006/inco.1996.0070.
  * [IL90] Neil Immerman and Eric Lander.  Describing graphs: A first-order approach to graph canonization.  In Alan L. Selman, editor, Complexity Theory Retrospective: In Honor of Juris Hartmanis on the Occasion of His Sixtieth Birthday, July 5, 1988, pages 59–81. Springer New York, New York, NY, 1990.  doi:10.1007/978-1-4612-4478-3_5.
  * [iOS06] Sang il Oum and Paul Seymour.  Approximating clique-width and branch-width.  Journal of Combinatorial Theory, Series B, 96(4):514–528, 2006\.  doi:10.1016/j.jctb.2005.10.006.
  * [IPZ01] Russell Impagliazzo, Ramamohan Paturi, and Francis Zane.  Which problems have strongly exponential complexity?  Journal of Computer and System Sciences, 63(4):512–530, 2001.  doi:10.1006/jcss.2001.1774.
  * [JKMT03] Birgit Jenner, Johannes Köbler, Pierre McKenzie, and Jacobo Torán.  Completeness results for graph isomorphism.  J. Comput. Syst. Sci., 66(3):549–566, may 2003.  doi:10.1016/S0022-0000(03)00042-4.
  * [KPS19] Sandra Kiefer, Ilia Ponomarenko, and Pascal Schweitzer.  The Weisfeiler–Leman dimension of planar graphs is at most 3.  J. ACM, 66(6), November 2019.  doi:10.1145/3333003.
  * [KST92] Johannes Köbler, Uwe Schöning, and Jacobo Torán.  Graph isomorphism is low for PP.  Comput. Complex., 2:301–330, 1992.  doi:10.1007/BF01200427.
  * [Kuc87] Ludek Kucera.  Canonical labeling of regular graphs in linear average time.  SFCS ’87, page 271–279, USA, 1987. IEEE Computer Society.  doi:10.1109/SFCS.1987.11.
  * [KV08] Johannes Köbler and Oleg Verbitsky.  From invariants to canonization in parallel.  In Edward A. Hirsch, Alexander A. Razborov, Alexei Semenov, and Anatol Slissenko, editors, Computer Science – Theory and Applications, pages 216–227, Berlin, Heidelberg, 2008. Springer Berlin Heidelberg.  doi:10.1007/978-3-540-79709-8_23.
  * [Lad75] Richard E. Ladner.  On the structure of polynomial time reducibility.  J. ACM, 22(1):155–171, January 1975.  doi:10.1145/321864.321877.
  * [Lib04] Leonid Libkin.  Elements of Finite Model Theory.  Springer, 2004.  doi:10.1007/978-3-662-07003-1_1.
  * [Lin92] Steven Lindell.  A logspace algorithm for tree canonization (extended abstract).  In Proceedings of the Twenty-Fourth Annual ACM Symposium on Theory of Computing, STOC ’92, page 400–404, New York, NY, USA, 1992. Association for Computing Machinery.  doi:10.1145/129712.129750.
  * [LPPS17] Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh.  Fixed-parameter tractable canonization and isomorphism test for graphs of bounded treewidth.  SIAM Journal on Computing, 46(1):161–189, 2017.  doi:10.1137/140999980.
  * [LRS23] Michael Levet, Puck Rombach, and Nicholas Sieger.  Logarithmic Weisfeiler–Leman and treewidth, 2023.  doi:10.48550/ARXIV.2303.07985.
  * [Luk82] Eugene M. Luks.  Isomorphism of graphs of bounded valence can be tested in polynomial time.  Journal of Computer and System Sciences, 25(1):42–65, 1982.  doi:10.1016/0022-0000(82)90009-5.
  * [Mat79] Rudolf Mathon.  A note on the graph isomorphism counting problem.  Information Processing Letters, 8(3):131–136, 1979.  doi:10.1016/0020-0190(79)90004-8.
  * [NS18] Daniel Neuen and Pascal Schweitzer.  An exponential lower bound for individualization-refinement algorithms for graph isomorphism.  In Ilias Diakonikolas, David Kempe, and Monika Henzinger, editors, Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 138–150. ACM, 2018.  doi:10.1145/3188745.3188900.
  * [Oum08] Sang-il Oum.  Rank-width is less than or equal to branch-width.  Journal of Graph Theory, 57(3):239–244, 2008.  doi:https://doi.org/10.1002/jgt.20280.
  * [Pon91] Ilia Ponomarenko.  The isomorphism problem for classes of graphs closed under contraction.  Journal of Mathematical Sciences, 55:1621–1643, 06 1991.  doi:10.1007/BF01098279.
  * [Sch88] Uwe Schöning.  Graph isomorphism is in the low hierarchy.  Journal of Computer and System Sciences, 37(3):312 – 323, 1988\.  doi:10.1016/0022-0000(88)90010-4.
  * [Smo87] Roman Smolensky.  Algebraic methods in the theory of lower bounds for boolean circuit complexity.  In Alfred V. Aho, editor, Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987, New York, New York, USA, pages 77–82. ACM, 1987.  doi:10.1145/28395.28404.
  * [Tor04] Jacobo Torán.  On the hardness of graph isomorphism.  SIAM J. Comput., 33(5):1093–1108, 2004.  doi:10.1137/S009753970241096X.
  * [Ver07] Oleg Verbitsky.  Planar graphs: Logical complexity and parallel isomorphism tests.  STACS’07, page 682–693, Berlin, Heidelberg, 2007. Springer-Verlag.  doi:10.5555/1763424.1763505.
  * [Wag11] Fabian Wagner.  Graphs of bounded treewidth can be canonized in $\textsf{AC}^{1}$.  In Proceedings of the 6th International Conference on Computer Science: Theory and Applications, CSR’11, page 209–222, Berlin, Heidelberg, 2011. Springer-Verlag.  doi:10.1007/978-3-642-20712-9_16.