Home/Magazine Archive/May 2021 (Vol. 64, No. 5)/Isomorphism, Canonization, and Definability for Graphs.../Full Text

Research highlights
# Isomorphism, Canonization, and Definability for Graphs of Bounded Rank Width

We investigate the interplay between the graph isomorphism problem, logical definability, and structural graph theory on a rich family of dense graph classes: graph classes of bounded rank width. We prove that the combinatorial Weisfeiler-Leman algorithm of dimension (3*k* + 4) is a complete isomorphism test for the class of all graphs of rank width at most *k.* A consequence of our result is the first polynomial time canonization algorithm for graphs of bounded rank width.

Our second main result addresses an open problem in descriptive complexity theory: we show that fixed-point logic with counting expresses precisely the polynomial time properties of graphs of bounded rank width.

The question of whether there is an efficient algorithm deciding whether two graphs are isomorphic is one of the oldest and best-known open problems in theoretical computer science. Already mentioned in Karp's^{18} seminal article on NP-complete combinatorial problems, graph isomorphism (from now on: GI) has remained one of the few natural problems in NP that is neither known to be solvable in polynomial time nor known to be NP-complete. The problem has received considerable attention recently because of Babai's^{1} breakthrough algorithm deciding GI in quasipolynomial time *n*^{polylog(n)}.

However, the question of whether GI is solvable in polynomial time remains wide open. Polynomial-time algorithms are known for the restrictions of GI to many interesting graph classes, for example the class of planar graphs^{14}, classes of bounded degree^{19}, even all classes excluding a fixed graph as a topological subgraph^{9}, and only recently, graph classes of bounded rank width.^{11}

*Rank width*, introduced by Oum and Seymour,^{21} is a graph invariant that measures how well a graph can be decomposed hierarchically in a certain style. In this respect, it is similar to the better-known tree width, but where tree width measures the complexity, or width, of a separation in a hierarchical decomposition in terms of the "connectivity" between the two sides, rank width measures the complexity of a separation in terms of the rank of the adjacency matrix of the edges between the two sides of the separation (see Figure 1). As opposed to tree width, rank width is also a meaningful measure of simplicity for dense graphs. For example, the rank width of a complete graph, arguably the simplest dense graph, is 1. Rank width is closely related to clique width,^{5} another well-studied graph invariant based on graph grammars. Many hard algorithmic problems can be solved efficiently on graphs of bounded rank width, or equivalently, bounded clique width, among them all problems definable in monadic second-order logic.^{4}

**Figure 1. A dense graph of rank width 2 (left) and a hierarchical "rank decomposition" of this graph of width 2 (right). The rank width is low because the vertex cuts the decomposition on the right induces are very regular.**

In this paper we study the graph isomorphism problem and the closely related graph canonization problem as well as logical definability and descriptive complexity on graph classes of bounded rank width. At the technical core of our work is a beautiful connection (from Cai et al.^{2}) between the Weisfeiler-Leman algorithm, a generic combinatorial graph isomorphism algorithm, and an Ehrenfeucht-Frässé style game that is usually used to prove lower bounds in logic.

Although a polynomial time isomorphism algorithm for graph classes of bounded rank width was known^{11} prior to this work, the running time of that algorithm is *n*^{f(k)}, where *n* is the number of vertices and *k* is the rank width of the input graph, and *f* is a *nonelementary* function. Moreover, the algorithm is extremely complicated, using both advanced techniques from structural graph theory^{12} and the group-theoretic graph isomorphism machinery.^{19}

Our first contribution is a simple isomorphism test for graphs of rank width at most *k* running in time *n*^{O(k)}. Indeed, the algorithm we use is a generic combinatorial isomorphism test known as the Weisfeiler-Leman algorithm.^{23, 1, 2} The *ℓ*-*dimensional Weisfeiler-Leman* algorithm (*ℓ*-WL) iteratively colors *ℓ*-tuples of vertices of the two input graphs and then compares the resulting color patterns. If they differ, we know that the two input graphs are nonisomorphic. If two graphs have the same color pattern, in general, they may still be nonisomorphic.^{2} Thus *ℓ*-WL is not a *complete* isomorphism test for all graphs. However, we prove that it is for graphs of bounded rank width. We say that *ℓ*-WL *identifies* a graph *G* if it distinguishes *G* from every graph *H* not isomorphic to *G.*

THEOREM 1. *The* (3*k* + 4)-*dimensional Weisfeiler-Leman algorithm identifies every graph of rank width at most k.*

Combining this theorem with a result due to Immerman and Lander on the running time of the WL algorithm, we obtain the following:

COROLLARY 2. *Isomorphism of graphs of rank width k can be decided in time O*(*n*^{3k+5} log *n*).

Another way of stating Theorem 1 is that the *Weisfeiler-Leman (WL) dimension*^{8} of graphs of rank width *k* is at most 3*k* + 4. It is known that many natural graph classes have bounded WL dimension, among them all classes of graphs excluding some fixed graph as a minor.^{8} But most of these classes consist of sparse graphs with an edge number linear in the number of vertices. Our result adds a rich family of classes that include dense graphs to the picture.

In many applications of graph isomorphism, it is actually necessary to compute a canonical representation of a graph, a so-called *canonical form*, rather than just decide if two graphs are isomorphic. A *canonical form* for a graph class *C* is a function *k*: *C* → *C* such that

*k*(*G*)≅*G*for all*G*∈*C*, and*k*(*G*)=*k*(*H*) for all isomorphic graphs*G*,*H*∈*C.*

Note that the isomorphism problem for a class *C* easily reduces to computing a canonical form for *C* (i.e., given a graph *G* ∈ *C*, compute *k*(*G*)). A reduction in the other direction is not known. However, it is known that if a class of graphs has WL dimension at most *ℓ* then there is an algorithm computing a canonical form for this class running in time *O*(*n*^{ℓ+3} log *n*). Hence, as another corollary to Theorem 1, we obtain the first polynomial-time canonization algorithm for graphs of bounded rank width.

COROLLARY 3. *There is an algorithm computing a canonical form for the class of graphs of rank width at most k in time O*(*n*^{3k+ 7} log *n*).

The second part of our paper is concerned with descriptive complexity theory, which aims to connect computational complexity and descriptive (or logical) complexity. The central open question of the field is whether there is a logic that *captures polynomial time.*^{3, 13} We will defer a more detailed discussion of this question and its background to Section 4 and at this point only state our main result.

THEOREM 4. *Fixed-point logic with counting* FP+C *captures polynomial time on every class of graphs of bounded rank width.*

On a very high level, the connection between the two theorems is that to prove Theorem 4 we mimic the proof of Theorem 1 within the realms of the logic FP+C.

The rest of this article is organized as follows: Section 2 is devoted to a thorough introduction to the Weisfeiler-Leman algorithm. In Section 3, we formally introduce rank width and informally sketch the proof of Theorem 1. Finally, Section 4 is devoted to descriptive complexity theory and Theorem 4.

**2.1. The color refinement algorithm**

One of the simplest combinatorial procedures to tackle the graph isomorphism problem is the color refinement algorithm. In a nutshell, the basic idea is to label vertices of the graph with their iterated degree sequence. More precisely, an initially uniform coloring is repeatedly refined by counting, for each color, the number of neighbors of that color.

Let *G* be a graph. Let χ_{1},χ_{2}:*V*(*G*)→*C* be colorings of vertices where *C* is some finite set of colors. The coloring *X*_{1} *refines* *X*_{2}, denoted by χ_{1} χ_{2}, if χ_{1}(*v*) = χ_{1}(*w*) implies χ_{2}(*v*) = χ_{2}(*w*) for all *v*, *w* ∈ *V*(*G*). The colorings *X*_{1} and *X*_{2} are *equivalent*, denoted by *X*_{1} ≡ *X*_{2}, if *X*_{1} *X*_{2} and *X*_{2} *X*_{1}.

We give a formal description of the color refinement algorithm. Initially, all vertices are assigned the same color. Formally, we define for all *v* ∈ *V*(*G*). Then, the coloring is iteratively refined as follows: for *i* > 0, we define where

is the multiset of colors for the neighbors computed in the previous round.

In each round, the algorithm computes a coloring that is finer than the one computed in the previous round, that is, . At some point, this procedure stabilizes meaning the coloring does not become strictly finer anymore. In other words, there is some minimal *i*^{*} ∈ N such that . We denote the corresponding coloring as the *stable* coloring and define . As an example, the sequence of colorings for a path of length 6 is depicted in Figure 2.

**Figure 2. The iterations of the color refinement algorithm on a path of length 6.**

The color refinement algorithm takes as input a graph *G* and outputs (a coloring that is equivalent to) *X ^{G}*. It can be implemented in almost linear time, that is, in time

One of the most common applications of the color refinement algorithm is to serve as a heuristic for GI. As the coloring computed by the color refinement algorithm is defined in an isomorphism-invariant manner, every isomorphism : *G* *H* between two graphs *G* and *H* satisfies that χ^{G}(*v*) = χ^{H} for all *v* ∈ *V* (*G*). The color refinement algorithm *distinguishes G* and *H* if there exists a color *c* such that

In order to determine algorithmically whether the color refinement algorithm *distinguishes G* and *H*, one typically runs the color refinement algorithm on the disjoint union of *G* and *H* and determines whether there is some color *c* that appears a different number of times in the two graphs.

If the color refinement algorithm does not distinguish *G* and *H*, we write *G* *H.* Note that

for all graphs *G* and *H.* Unfortunately, the backward direction of the implication does not hold. For example, the color refinement algorithm does not distinguish the disjoint union of two triangles from a cycle of length six although the two graphs are nonisomorphic.

Still, despite its simplicity, the color refinement algorithm serves as a complete isomorphism test for a large number of graphs. We say the color refinement algorithm *identifies* a graph *G* if it distinguishes *G* from every other nonisomorphic graph *H.* For example, it is known that the color refinement algorithm identifies random graphs asymptotically almost surely.

In combination with its efficiency, this makes the color refinement algorithm a popular subroutine in the context of GI, which is used in many practical and theoretical algorithms.

**2.2. The k-dimensional algorithm**

Although the color refinement algorithm often serves as a complete isomorphism test, it is still quite restricted in its power. For example, given any two *d*-regular graphs *G* and *H*, the color refinement algorithm does not distinguish *G* and *H.* The *Weisfeiler-Leman algorithm* provides an extension to the color refinement algorithm, which, instead of only coloring single vertices, colors *k*-tuples of vertices for some fixed number *k.* This gives the algorithm additional expressive power for increasing values of *k*, but comes at the price of higher computational complexity.

Let *G* be a graph and let *k* ∈ N. The *k-dimensional Weisfeiler-Leman algorithm* (*k*-WL) is a procedure that, given a graph *G*, first computes an isomorphism-invariant initial coloring of the *k*-tuples of vertices and then iteratively refines this coloring in an isomorphism-invariant way. The 1-dimensional Weisfeiler-Leman algorithm corresponds exactly to the color refinement algorithm described above.

For the description of the algorithm for higher dimensions, fix *k* ≥ 2 and let *G* = (*V*, *E*) be a graph. The initial coloring computed by *k*-WL determines for each ∈*V*^{k} the isomorphism-type of the underlying ordered induced subgraph. More precisely, if for all *i*, *j* ∈ [*k*] it holds *v _{i}* =

From the definition of the colorings, it is immediately clear that . Now let *i*^{*} ∈ N be the minimal number such that . For this *i*^{*}, the coloring is called the *stable* coloring of *G* with respect to *k*-WL and is denoted by *X ^{G,k}*.

As an example, the coloring *X*^{G,2} where *G* is a cycle of length 9 is depicted in Figure 3.

**Figure 3. The stable coloring of 2-WL on a cycle of length 9. In this example, χ ^{G,2}(v, w)=χ^{G,2} (w,v) for all v, w ∈ V (G) and thus, all colors are represented by undirected edges.**

The *k-dimensional Weisfeiler-Leman algorithm* takes as input a graph *G* and computes (a coloring that is equivalent to) *X ^{G,k}*.

THEOREM 5 (Immerman and Lander^{17}). *Let G be a graph. Then, an isomorphism-invariant coloring that is equivalent to X ^{G,k} can be computed in time O*(

We extend the notations introduced for the color refinement algorithm. The *k*-dimensional Weisfeiler-Leman algorithm *distinguishes* two graphs *G* and *H* if there is a color *c* such that |(χ^{G,k})^{−1}(*c*)|≠|(χ^{H,k})^{−1}(*c*)|. In this case it follows that *G* and *H* are nonisomorphic. Two graphs *G* and *H* are *equivalent* with respect to *k*-WL, denoted by *G* _{k} *H*, if they are not distinguished by *k*-WL. A graph *G* is *identified* by *k*-WL if *G* _{k} *H* if and only if *G* ≅ *H* for all graphs *H.* The *Weisfeiler-Leman dimension* of a graph *G* is the smallest number *k* ∈ N such that *k*-WL identifies *G.*

**2.3. A pebble game**

Providing upper bounds on the Weisfeiler-Leman dimension of certain graphs often turns out to be rather complicated when arguing directly with the definition of the Weisfeiler-Leman algorithm. Indeed, it is often more convenient to exploit other characterizations of the power of the Weisfeiler-Leman algorithm for this task. In particular, the following pebble game is known to capture the same information as the Weisfeiler-Leman algorithm.

Let *k* ∈ *N.* For graphs *G*, *H* on the same number of vertices, we define the *bijective k-pebble game* BP_{k} (*G*, *H*) as follows:

- The game has two players called Spoiler and Duplicator.
- The game proceeds in rounds. Each round is associated with a pair of positions with ∈
*V*(*G*)^{ℓ}and where 0≤*ℓ*≤*k*. - The initial position of the game is ((), ()) (the pair of empty tuples).
- Each round consists of the following steps: Suppose the game is in position . First, Spoiler chooses whether to remove a pair of pebbles or to play a new pair of pebbles. The first option is only possible if
*ℓ*> 0 and the latter option is only possible if*ℓ*<*k.*

- If Spoiler wishes to remove a pair of pebbles, he picks some
*i*∈ [*ℓ*] and the game moves to position where \*i*:=(*v*_{1},…,*v*_{i−1},*v*_{i+1},…,*v*_{ℓ}) (and is defined in the same way). - Otherwise, a new pair of pebbles is played and the following steps are performed:
- (D) Duplicator picks a bijection
*f*:*V*(*G*) →*V*(*H*). - (S) Spoiler chooses
*v*∈*V*(*G*) and sets*w*:=*f*(*v*). - The new position is ((
*v*_{1},…,*v*_{ℓ},*v*), (*w*_{1},…,*w*_{ℓ},*w*)). - Spoiler wins the play if for the current position the induced graphs are not isomorphic. More precisely, Spoiler wins if there are
*i*,*j*∈[*ℓ*] such that*v*_{i}=*v*_{j}*w*_{i}=*w*_{j}or*v*_{i}*v*_{j}∈*E*(*G*)*w*_{i}*w*_{j}∈*E*(*H*). If the play never ends, Duplicator wins.

We say that Spoiler (resp. Duplicator) *wins the bijective k-pebble game* BP_{k} (*G*, *H*) if Spoiler (resp. Duplicator) has a winning strategy for the game.

Moreover, for positions Spoiler (resp. Duplicator) *wins the game* BP_{k} (*G*, *H*) *from position* if Spoiler (resp. Duplicator) has a winning strategy in the game BP_{k}(*G*, *H*) starting from initial position .

The next theorem connects the bijective *k*-pebble game to the Weisfeiler-Leman algorithm.

THEOREM 6 (Cai et al.^{2}). *Let G*, *H be two graphs and let* ∈*V*(*G*)^{k} *and . Then if and only if Duplicator wins the pebble game* BP_{k+1} (*G*, *H*) *from the position* .

COROLLARY 7. *Let G, H be two graphs. Then G* _{k} *H if and only if Duplicator wins the pebble game* BP_{k+1} (*G*, *H*).

Rank width is a graph invariant that was first introduced by Oum and Seymour^{21} and that measures the width of a certain style of hierarchical decomposition of graphs. Intuitively, the aim is to repeatedly split the vertex set of the graph along cuts of low complexity in a hierarchical fashion. For rank width, the complexity of a cut is measured in terms of the rank of the matrix capturing the adjacencies between the two sides of the cut over the 2-element field F_{2}.

Let *G* be a graph. For *X*, *Y* ⊆ *V* (*G*), we define where (*M*(*X*, *Y*))_{x,y} = 1 if and only if *xy* ∈ *E*(*G*). Furthermore, where and rk_{2}(*A*) denotes the F_{2}-rank of a matrix *A.*

A *rank decomposition* of *G* is a tuple (*T*, *γ*) consisting of a binary directed tree *T* and a mapping *γ* : *V*(*T*) → 2^{V(G)} such that

(R.1) *γ*(*r*) = *V* (*G*) where *r* is the root of *T*,

(R.2) *γ*(*t*)=*γ*(*t*_{1})∪ *γ*(*t*_{2}) and *γ*(*t*_{1})∩ *γ*(*t*_{2})=/ for all internal nodes *t* ∈ *V*(*T*) with children *t*_{1} and *t*_{2}, and

(R.3) |*γ*(*t*)| = 1 for all *t* ∈ *L* (*T*), where *L* (*T*) denotes the set of leaves of the tree *T.*

Note that, instead of giving *γ*, we can equivalently specify a bijection *f* : *L*(*T*) → *V*(*G*) (this completely specifies *γ* by Condition (R.2) ). The *width* of a rank decomposition (*T*, *γ*) is

The rank width of a graph *G* is

Examples of graphs *G* and rank decompositions of *G* are provided in Figure 1 and (more detailed) in Figure 4.

**Figure 4. A graph G on the left and a potential rank decomposition of G of width 3 on the right. As an example, the matrix M({6, 7, 8, 9, 10}, {1, 2, 3, 4, 5}) is provided. Note that ρ_{G}({6, 7, 8, 9, 10]) = 3.**

Clique width^{5} is another measure aiming to describe the structural complexity of a graph. It is based on a natural graph grammar.

For *k* ∈ N, a *k-graph* is a pair (*G*, lab) where *G* is a graph and lab: *V*(*G*) → [*k*] is a labeling of vertices. We define the following four operations for *k*-graphs:

- For
*i*∈ [*k*], let •_{i}denote an isolated vertex with label*i.* - For
*i*,*j*∈ [*k*] with*i*≠*j*, we define η_{i,j}(*G*, lab) := (*G'*, lab) where*V*(*G*) :=*V*(*G'*) and*E*(*G'*) :=*E*(*G*) ∪ {*vw*| lab(*v*) =*i*∧ lab(*w*) =*j*}. - For
*i*,*j*∈ [*k*], we define*ρ*_{i→j}(*G*, lab := (*G*, lab') where . - For two
*k*-graphs (*G*, lab) and (*G'*, lab'), we define (*G*, lab) ⊕ (*G'*, lab') to be the disjoint union of the two*k*-graphs.

A *k-expression t* is a well-formed expression in these symbols and defines a *k*-graph (*G*, lab). In this case, *t* is a *k*-expression for *G.* The clique width of a graph *G*, denoted by cw(*G*), is the minimum *k* ∈ N such that there is a *k*-expression for *G.*

*Example 1.* The expression

is a 2-expression for the graph in Figure 1. The colors of the "constants" •_{i} indicate which node in the figure they correspond to.

Comparing clique width and rank width, each parameter is bounded in terms of the other.^{21} More precisely, for every graph *G*, it holds that

Also, the rank width of a graph *G* is bounded by the tree width of *G*, denoted by tw(*G*), by rw(*G*) ≤ tw(*G*) + 1. Note that the tree width of a graph cannot be bounded in terms of its rank width. For example, the complete graph on *n* vertices *K _{n}* has rank width rw(

**3.1 The WL dimension of graphs of bounded rank width**

The first main result of this work bounds the Weisfeiler-Leman dimension of graphs of rank width at most *k* by a linear function in *k.*

THEOREM 8. *The* (3*k* + 4)-*dimensional Weisfeiler-Leman algorithm identifies every graph of rank width at most k.*

Note that, by Equation (1), the same result and all of its consequences also hold for graphs of clique width at most *k.*

For the remainder of this section, we provide a high-level sketch of the proof of Theorem 8. We need to argue that, for every two nonisomorphic graphs *G* and *H* such that rw(*G*) ≤ *k*, the (3*k* + 4)-dimensional Weisfeiler-Leman algorithm distinguishes between *G* and *H.* Exploiting the characterization of *k*-WL in terms of pebble games (see Corollary 7), it actually suffices to show that Spoiler wins the bijective {3*k* + 5)-pebble game BP_{3k+5} (*G*, *H*).

To describe Spoiler's strategy, let us fix the input graphs *G* and *H* as well as some rank decomposition (*T*, *γ*) of *G* of width at most *k.* The basic idea for Spoiler is to play along the rank decomposition of *G* in a downward fashion in order to confine the "difference" between the two input graphs to smaller and smaller regions of the graphs. More precisely, for his strategy, Spoiler maintains sets *X*_{G} ⊆ *V*(*G*) and *X*_{H} ⊆ *V*(*H*) and vertices and where *p* ≤ *k* such that there is no isomorphism : *G*[*X*_{G}] → *H*[*X*_{H}] with and (where *G*[*X _{G}*] and

During the play, the set *X _{G}* essentially corresponds to the sets

In order to force a descend in the rank decomposition, Spoiler's goal is to move to one of the two children *t*_{1}, *t*_{2} of *t* in the rank decomposition (*T*, *γ*). To maintain the invariant described above, it is necessary to "split" *γ*(*t*_{1}) from *γ*(*t*_{2}) in the graph *G* in such a way that there are no dependencies left between the two sets. This enables Spoiler to confine the "difference" between the two input graphs to one of the two sides. To achieve the "split", we introduce the notion of a *split pair.*

Let *G* be a graph and *X* ⊆ *V*(*G*). For *v*, *w* ∈ *X*, we define *v*≈_{X} *w* if . For *v* ∈ *X*, we define the vector where *a*_{v,w} = 1 if and only if *vw* ∈ *E*(*G*). Note that *v*≈_{X} *w* if and only if vec_{x} (*v*) = vec_{x} (*w*). Moreover, for *A* ⊆ *X*, we define vec_{x} (*A*) = {ven_{X} (*v*)|*v*∈*A*}.

For any set of vectors , we denote by *S* the linear space spanned by *S.* A set is a *linear basis for* *S* if *B* is linearly independent and *B* = *S*.

*Definition 1.* Let *G* be a graph and *X* be a graph and *V*(*G*). A pair (*A*, *B*) is a *split pair for X* if

*A*⊆*X*and ,- vec
_{x}(*A*) forms a linear basis for ven_{x}(*X*), and - forms a linear basis for .

Note that |*A*| = *ρ*_{G}(*X*) and |*B*| = *ρ*_{G}(*X*). Also observe that if (*A*, *B*) is a split pair for *X* then (*B*, *A*) is a split pair for . As a special case, the pair (/,/) is defined to be a split pair for *X* = *V*(*G*). An *ordered split pair for X* is a pair such that ({*a*_{1}, …, *a*_{p}}, {*b*_{1},…,*b*_{p}}) is a split pair for *X.*

Now the central claim for split pairs is that pebbling an ordered split pair for *X* renders *X* to be "independent" from its complement. In order to visualize this independence, we make use of the color refinement algorithm. Toward this end, we define to be the coloring computed by the color refinement algorithm on the graph *G* where all vertices *a*_{1}, …, *a _{p}*,

*Definition 2.* Let *G* = (*V*, *E*) be a graph and *X* *V* → *C* a coloring of the vertices. A *flip function for G* is a mapping *f*: *C* × *C* → {0, 1} such that *f*(*c*,*c*')=*f*(*c*',*c*) for all *c*, *c'* ∈ *C.*

For a flip function *f*, we define the flipped graph *G ^{f}* = (

The following lemma gives the key tool to split *X* from its complement. For a graph *G* and a flip function *f*, let Comp(*G*, *f*) ⊆ 2^{V(G)} be the set of vertex sets of the connected components of *G ^{f}*. Observe that Comp(

LEMMA 9. *Let G* = (*V*, *E*) *be a graph and X* ⊆ *V. Also let* *be an ordered split pair for X.*

*Then there is a flip function f for the graph G with coloring such that for every C* ∈ Comp(*G*, *f*) *it holds that C* ⊆ *X or* .

This process is also visualized in Figure 5 taking as input the example from Figure 1.

**Figure 5. In order to split X from its complement in the graph G (top Left), we individualize a split pair (top right), compute the coloring using the color refinement algorithm (bottom left), and apply a suitable flip function to the graph (bottom right).**

As applying a flip function to both input graphs changes neither the isomorphism problem nor the outcome of the bijective pebble game, Spoiler can simply pretend he is playing on *G ^{f}* and

Now, in order to force a descend step in the rank decomposition, Spoiler pebbles split pairs for the sets *γ*(*t*_{1}) and *γ*(*t*_{2}) in order to render these sets to be independent from the rest of the graph. This allows Spoiler to track the difference between both input graphs to one of the two sets.

This almost completes the descend step. Indeed, the only remaining task for Spoiler is to remove all pebbles from previous steps to ensure that the number of required pebbles does not exceed 3*k* + 5. In particular, the pebbles placed on the vertices of a split pair for *γ*(*t*) need to be removed.

However, it is not possible to simply remove these pebbles since, by the invariant described above, the sets *X _{G}* and

*Definition 3.* Let *G* be a graph and *X*, *X*_{1}, *X*_{2} ⊆ *V*(*G*) such that *X* = *X*_{1} ∪ *X*_{2} and *X*_{1} ∩ *X*_{2} = /. Let (*A*, *B*) be a split pair of *X* and let (*A _{i}*,

*A*∩*X*_{i}⊆*A*_{i}, and*B*_{3−i}∩*X*_{i}⊆*A*_{i}for both*i*∈ {1, 2}.

Naturally, a triple of ordered split pairs is nice if the underlying unordered triple of split pairs is nice.

Intuitively speaking, nice triples of split pairs enforce a significant overlap of all considered split pairs when performing the descend step. This enables Spoiler to remove the pebbles from the previous descend step without unpebbling any vertex in *X _{G}* or

LEMMA 10. *Let G be a graph and X*, *X*_{1}, *X*_{2} ⊆ *V*(*G*) *such that X* = *X*_{1} ∪ *X*_{2} *and X*_{1} ∩ *X*_{2} = /. *Let* (*A*, *B*) *be a split pair of X. Then there are nice split pairs* (*A _{i}*,

Hence, in all steps, Spoiler can play a nice triple of split pairs and simply remove any unwanted pebbles following the completion of a descend step while preserving the invariant given above. This completes the description of the strategy.

Descriptive complexity theory aims to characterize computational complexity in terms of logical definability, that is, relate computational resources such as space and time to language resources such as recursion mechanisms or quantifier alternation. The best-known result in the field is Fagin's theorem^{7} stating existential second-order logic captures NP, that is, a property of graphs (or other structures) is decidable in nondeterministic polynomial time if and only if it is definable in existential second-order logic. The best-known open problem, going back to Chandra and Harel's influential paper^{3} on database query languages and popularized by Gurevich,^{13} asks whether there is a logic that captures PTIME (polynomial time). In the following, we give a very brief introduction to the relevant notions and results from descriptive complexity. For more background, we refer the reader to the existing literature (e.g., Ebbinghaus and Flum^{6}).

In descriptive complexity theory, computational problems are typically modeled using finite relational structures, for example, graphs. A decision problem is simply a *property of structures*, that is, a class of structures that is closed under isomorphism. Closure under isomorphism is important, because it means that properties are isomorphism-invariant. For example, "a graph is connected" is a valid property, whereas "the first vertex has degree 3" is not, because a graph has no well-defined "first vertex". An *abstract logic* L is simply a set of sentences together with a satisfaction relation between structures and sentences. An abstract logic L *captures* PTIME if (i) it has a decidable syntax (the set of sentences is a decidable set of strings over a finite alphabet); (ii) it has a PTIME-decidable semantics, in the sense that there is an algorithm that, given a sentence of L and a structure *A*, decides if *A* satisfies in time polynomial in the size of *A*; and (iii) every PTIME-decidable property *P* of structures is definable in L, that is, there is a sentence of L that is satisfied by precisely those structures that have property *P*. We say L captures PTIME *on a class C of structures* if condition (iii) is satisfied for all properties *P* ⊆ *C.*

Although there are good reasons to define an abstract logic capturing PTIME this way (see Gurevich^{13}), the reason we are interested in a logical characterization of PTIME is the hope that it might give us new insights into the mechanisms of efficient computation. For this, we are not so interested in an abstract logic, but rather in nice logical languages with few clearly understood operators. Logics that have proved to be natural and useful in this regard are extensions of classical first-order logic FO by fixed-point operators allowing it to formalize iterative or recursive definitions. *Inflationary fixed-point logic* FP is a robust extension of FO with a fixed-point operator that allows it to define a relation by iteratively adding tuples to the initially empty relation.

*Example 2.* The FP-sentence conn defined as

expresses that a graph is connected. For any two nodes *x*, *y*, the ifp(…) operator computes the connected component *X* of *x* by adding *x* and then in each iteration all neighbors of nodes already in *X.* Then the sentence conn says that for all *x*, *y*, *y* belongs to the connected component *X* of *x.*

Often, it is useful to also add rudimentary arithmetic to the logic, in particular, the ability to count. *Inflationary fixed-point logic with counting* FP+C is an extension of FP by the ability to speak about an initial segment of the natural numbers with basic arithmetic and a counting mechanism relating structures and numbers.

*Example 3.* The following FP+C-sentence defines the class of Eulerian graphs (i.e., graphs with a cyclic walk that traverses all edges, which are well-known to be exactly the connected graphs in which all vertices have even degree):

Here conn is the sentence defined in the previous example, #*y* *E*(*x*, *y*) defines the number of nodes *y* that are adjacent to node *x*, and even (*n*) is a formula expressing that *n* is an even number.

So FP and FP+C extend first-order logic, which provides the basic logical machinery, by two fundamental computational mechanisms: iteration and counting. At first sight, it may seem that counting the number of elements in a set, for example, the set of neighbors of a vertex in a graph, can be simulated by enumerating the elements in an iterative process implemented in FP. But this assumes that the elements of the set can be put in some order, and such an order is not always available in a structure. Logics operate in an isomorphism-invariant way, and there may be no isomorphism-invariant order on our set.

Although FP and FP+C fail to capture PTIME—this is easy to prove for FP and surprisingly hard for FP+C^{2}—it has been shown that they can express many natural PTIME-properties and they do capture PTIME restricted to a large variety of classes of structures. As a starting point, Immerman^{15} and independently Vardi^{22} proved that FP captures PTIME on the class of ordered structures, that is, structures that have one relation, which is a linear order of the universe. Note that on ordered structures we can simulate counting using iteration, and thus, FP and FP+C have the same expressive power. As soon as we leave ordered structures, we need the explicit counting mechanism of FP+C. In a series of papers that culminated in a monograph,^{8} it was proved that FP+C captures PTIME on all graph classes that exclude a fixed graph as a minor. In particular, this includes the class of planar graphs and all graph classes of bounded tree width. Not too much is known beyond these classes, which all consist of sparse graphs. Indeed, looking at dense graphs, there are only very few examples of classes for which it is known that FP+C captures PTIME, most of which are fairly restricted classes of intersection graphs (e.g., interval graphs and permutation graphs). Our second main result, Theorem 4 stating that FP+C captures PTIME on all graph classes of bounded rank width, broadens the scope of these results into a new direction.

Like previous results of this type, Theorem 4 is proved using the framework of *definable canonization.*^{8,20} Recall that by the Immerman-Vardi theorem,^{16, 22} FP captures polynomial time on the class of all ordered structures. A straightforward way of applying this theorem to a class *C* of unordered structures is to define a linear order on this class: if there is a formula ord(*x*, *y*) of the logic FP that defines a linear order on all structures in *C*, then FP still captures polynomial time on *C.* Unfortunately, this observation is rarely applicable, because usually it is impossible to define linear orders. For example, it is impossible to define a linear order on a structure that has a nontrivial automorphism.

A more refined idea, known as *definable canonization*, is to define an *ordered copy* of the input structure. To implement this idea, FP+C is particularly well-suited, because it allows us to speak about an initial segment of the natural numbers that comes with a natural linear order. Technically, definable canonization is based on syntactical interpretations, which allow it to define a structure within another structure using logical formulas. (In database terminology, a syntactical interpretation would be a view.)

Without going into any details, let us just state that the main technical lemma toward the proof of Theorem 4 states that for all *k* the class of all graphs of rank width *k* admits FP+C -definable canonization. The idea to prove this lemma is to implement our canonization procedure for graphs of rank width *k* based on the (3*k* + 4)-dimensional Weisfeiler-Leman algorithm by a formula of the logic FP+C.

For all further details, we refer the reader to the full version of this article.^{10}

In this article, we considered the isomorphism and canonization problem for graphs of bounded rank width. The first main result is that the Weisfeiler-Leman dimension of graphs of rank width at most *k* is at most 3*k* + 4. This implies that isomorphism testing and computing canonical forms for graphs of rank width at most *k* can be done in time *n*^{O(k)}.

Naturally, it would be desirable to further improve on the complexity of the two problems. Indeed, an important open question is whether isomorphism testing is also fixed-parameter tractable when parameterized by rank width (i.e., whether there is an algorithm testing isomorphism of graphs of rank width at most *k* in time *f*(*k*)*n ^{c}* for some computable function

The second main result states that, for every *k* ∈ N, fixed-point logic with counting captures PTIME on the class of graphs of rank width at most *k*.

1. Babai, L. Graph isomorphism in quasipolynomial time [extended abstract]. In *Proceedings of the 48 ^{th} Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18–21, 2016* (2016), D. Wichs and Y. Mansour eds. ACM, 684–697.

2. Cai, J., Fürer, M., Immerman, N. An optimal lower bound on the number of variables for graph identifications. *Combinatories 4*, 12 (1992), 389–410.

3. Chandra, A.K., Harel, D. Structure and complexity of relational queries. *J. Comput. Syst. Sci. 1*, 25 (1982), 99–128.

4. Courcelle, B., Makowsky, J.A., Rotics, U. Linear time solvable optimization problems on graphs of bounded clique-width. *Theory Comput. Syst. 2*, 33 (2000), 125–150.

5. Courcelle, B., Olariu, S. Upper bounds to the clique width of graphs. *Discrete Appl. Math. 1–3*, 101 (2000), 77–114.

6. Ebbinghaus, H., Flum, J. *Finite Model Theory*, 2^{nd} edn. Springer Verlag, 1999.

7. Fagin, R. Generalized first-order spectra and polynomial-time recognizable sets. In *Complexity of Computation, SIAM-AMS Proceedings* (Vol. 7), R. Karp, ed. (1974), 43–73.

8. Grohe, M. Descriptive complexity, canonisation, and definable graph structure theory. Volume 47 of *Lecture Notes in Logic.* Cambridge University Press, 2017.

9. Grohe, M., Marx, D. Structure theorem and isomorphism test for graphs with excluded topological subgraphs. *SIAM J. Comput. 1*, 44 (2015), 114–159.

10. Grohe, M., Neuen, D. Canonisation and definability for graphs of bounded rank width. *CoRR*, abs/1901.10330, 2019.

11. Grohe, M., Schweitzer, P. Isomorphism testing for graphs of bounded rank width. In *IEEE 56 ^{th} Annual Symposium on Foundations of Computer Science, FOCS 2015* (Berkeley, CA, USA, October 17–20, 2015), V. Guruswami, ed. IEEE Computer Society, 1010–1029.

12. Grohe, M., Schweitzer, P. Computing with tangles. *SIAM J. Discrete Math. 2*, 30 (2016), 1213–1247.

13. Gurevich, Y. Logic and the challenge of computer science. In *Current Trends in Theoretical Computer Science* (1988), E. Börger, ed. Computer Science Press, 1–57.

14. Hopcroft, J.E., Tarjan, R. Efficient planarity testing. *J. ACM*, 21 (1974), 549–568.

15. Immerman, N. Relational queries computable in polynomial time (extended abstract). In *Proceedings of the 14 ^{th} ACM Symposium on Theory of Computing* (1982), 147–152.

16. Immerman, N. Languages that capture complexity classes. *SIAM J. Comput. 4*, 16 (1987), 760–778.

17. Immerman, N., Lander, E. Describing graphs: A first-order approach to graph canonization. In *Complexity Theory Retrospective: In Honor of Juris Hartmanis on the Occasion of His Sixtieth Birthday* (July 5, 1988), A.L. Selman, ed. Springer New York, New York, NY, 1990, 59–81.

18. Karp, R. On the complexity of combinatorial problems. *Networks*, 5 (1975), 45–68.

19. Luks, E.M. Isomorphism of graphs of bounded valence can be tested in polynomial time. *J. Comput. Syst. Sci. 1*, 25 (1982), 42–65.

20. Otto, M. Bounded variable logics and counting—A study in finite models. Volume 9 of *Lecture Notes in Logic.* Springer, 1997.

21. Oum, S., Seymour, P.D. Approximating clique-width and branch-width. *J. Comb. Theory, Ser. B 4*, 96 (2006), 514–528.

22. Vardi, M.Y. The complexity of relational query languages (extended abstract). In *Proceedings of the 14th Annual ACM Symposium on Theory of Computing* (San Francisco, California, USA, May 5–7, 1982), H. R. Lewis, B. B. Simons, W. A. Burkhard, and L. H. Landweber, eds. ACM, 1982, 137–146.

23. Weisfeiler, B., Leman, A. The reduction of a graph to canonical form and the algebra which appears therein. *NTI Ser. 2*, 1968. Available at *htttps://www.iti.zcu.cz/wl2018/pdf/wl_paper_translation.pdf.* English transalation by G. Ryabov

A previous version of this paper, entitled "Canonisation and Definability for Graphs of Bounded Rank Width" was published in *Proceedings of the 34 ^{th} Annual ACM/IEEE Symp. on Logic in Computer Science* (Vancouver, BC, Canada, 2019), 1–13.

Copyright held by authors/owners. Publication rights licensed to ACM.

Request permission to publish from permissions@acm.org

The Digital Library is published by the Association for Computing Machinery. Copyright © 2021 ACM, Inc.

No entries found