Communications of the ACM

Research highlights

Isomorphism, Canonization, and Definability for Graphs of Bounded Rank Width

By Martin Grohe, Daniel Neuen
Communications of the ACM, May 2021, Vol. 64 No. 5, Pages 98-105
10.1145/3453943
Comments

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 (3k + 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.

Back to Top

1. Introduction

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¹⁸ 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¹ 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¹⁴, classes of bounded degree¹⁹, even all classes excluding a fixed graph as a topological subgraph⁹, and only recently, graph classes of bounded rank width.¹¹

Rank width, introduced by Oum and Seymour,²¹ 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,⁵ 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.⁴

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.²) 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¹¹ 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¹² and the group-theoretic graph isomorphism machinery.¹⁹

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.² 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 (3k + 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⁸ of graphs of rank width k is at most 3k + 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.⁸ 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

1. k(G)≅G for all G ∈ C, and
2. 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.

Back to Top

2. Weisfeiler-Leman Algorithm

 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 χ₁,χ₂:V(G)→C be colorings of vertices where C is some finite set of colors. The coloring X₁ refines X₂, denoted by χ₁ ⪯ χ₂, if χ₁(v) = χ₁(w) implies χ₂(v) = χ₂(w) for all v, w ∈ V(G). The colorings X₁ and X₂ are equivalent, denoted by X₁ ≡ X₂, if X₁ ⪯ X₂ and X₂ ⪯ X₁.

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 O((n + m) log n) where n denotes the number of vertices and m the number of edges of G.

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 = v_j if and only if w_i = w_j, and v_iv_j∈E if and only if w_iw_j∈E. The initial coloring is refined by iteratively computing colorings for i > 0. For ῡ=(v₁,…,v_k) and w ∈ V, let ῡ[i/w]:=(v₁,…,v_i−1,w,v_i+1,…,v_k) be the tuple obtained from ῡ by replacing the i-th entry with vertex w. Now we define where

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¹⁷). Let G be a graph. Then, an isomorphism-invariant coloring that is equivalent to X^G,k can be computed in time O(n^k+1 log n).

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)⁻¹(c)|≠|(χ^H,k)⁻¹(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₁,…,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₁,…,v_ℓ,v), (w₁,…,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_iv_j∈E(G) ⇎ w_iw_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.²). 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).

Back to Top

3. Rank Width

Rank width is a graph invariant that was first introduced by Oum and Seymour²¹ 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₂.

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₂(A) denotes the F₂-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₁)∪ γ(t₂) and γ(t₁)∩ γ(t₂)=/ for all internal nodes t ∈ V(T) with children t₁ and t₂, 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⁵ 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:

1. For i ∈ [k], let •_i denote an isolated vertex with label i.
2. 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}.
3. For i,j ∈ [k], we define ρ_i→j (G, lab := (G, lab') where .
4. 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.²¹ 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(K_n) = 1 and tree width tw(K_n) = n − 1.

 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 (3k + 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 (3k + 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 {3k + 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 H[X_H] denote the induced subgraphs on vertex sets X_G and X_H). By gradually decreasing the size of the set X_G, Spoiler eventually wins the game since, as soon as |X_G| ≤ 2k + 1, the entire set X_G can be pebbled.

During the play, the set X_G essentially corresponds to the sets γ(t) where t ∈ V(T) is a node of the rank decomposition of G where, as the play progresses, Spoiler moves down the rank decomposition to enforce a decrease in the size of the set X_G. Initially, X_G := V(G), X_H =: V(H), p = 0, and t is the root node of the rank decomposition of G.

In order to force a descend in the rank decomposition, Spoiler's goal is to move to one of the two children t₁, t₂ of t in the rank decomposition (T, γ). To maintain the invariant described above, it is necessary to "split" γ(t₁) from γ(t₂) 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

1. A ⊆ X and ,
2. vec_x (A) forms a linear basis for 〈ven_x (X)〉, and
3. 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₁, …, a_p}, {b₁,…,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₁, …, a_p, b₁, …, b_p are individualized initially (i.e., each of the listed vertices is assigned a fresh color that is distinct from the colors of all other vertices). Moreover, we consider the notion of a flip function that allows us to flip edges between certain color classes of the coloring .

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 = (V, E^f) where

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(G, f) forms a partition of the vertex set of G.

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 H^f instead of G and H. For G^f and H^f, Spoiler can now restrict the game to a pair of connected components of the two graphs X_G ⊆ V(G) and X_H ⊆ V(H), marking both components by placing a single pebble on them.

Now, in order to force a descend step in the rank decomposition, Spoiler pebbles split pairs for the sets γ(t₁) and γ(t₂) 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 3k + 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 X_H are only assured to be nonisomorphic as long as as well as are pebbled (these vertices need to be temporarily fixed to allow for the applications of Lemma 9). In order to circumvent this problem, we introduce the notion of nice triples of split pairs.

Definition 3. Let G be a graph and X, X₁, X₂ ⊆ V(G) such that X = X₁ ∪ X₂ and X₁ ∩ X₂ = /. Let (A, B) be a split pair of X and let (A_i, B_i) be split pairs for X_i, i ∈ {1, 2}. We say that (A_i, B_i), i ∈ {1, 2}, are nice (with respect to (A, B)) if

1. A∩X_i⊆A_i, and
2. 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 X_H. The following lemma guarantees the existence of nice triples of split pairs.

LEMMA 10. Let G be a graph and X, X₁, X₂ ⊆ V(G) such that X = X₁ ∪ X₂ and X₁ ∩ X₂ = /. Let (A, B) be a split pair of X. Then there are nice split pairs (A_i, B_i) for X_i for both i ∈ {1, 2}.

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.

Back to Top

4. Descriptive Complexity

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⁷ 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³ on database query languages and popularized by Gurevich,¹³ 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⁶).

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¹³), 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²—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¹⁵ and independently Vardi²² 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,⁸ 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 (3k + 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.¹⁰

Back to Top

5. Conclusion

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 3k + 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 f and an absolute constant c).

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.

Back to Top

Back to Top

Back to Top

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

---

No entries found