acm-header
Sign In

Communications of the ACM

Research highlights

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


isomorphic graph

Credit: Bhavana

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's18 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's1 breakthrough algorithm deciding GI in quasipolynomial time npolylog(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 graphs14, classes of bounded degree19, even all classes excluding a fixed graph as a topological subgraph9, 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

f1.jpg
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 known11 prior to this work, the running time of that algorithm is nf(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 theory12 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 nO(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 (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(n3k+5 log n).

Another way of stating Theorem 1 is that the Weisfeiler-Leman (WL) dimension8 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.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: CC such that

  1. k(G)≅G for all GC, and
  2. k(G)=k(H) for all isomorphic graphs G, HC.

Note that the isomorphism problem for a class C easily reduces to computing a canonical form for C (i.e., given a graph GC, 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(n3k+ 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 χ12:V(G)→C be colorings of vertices where C is some finite set of colors. The coloring X1 refines X2, denoted by χ1 ⪯ χ2, if χ1(v) = χ1(w) implies χ2(v) = χ2(w) for all v, wV(G). The colorings X1 and X2 are equivalent, denoted by X1X2, if X1X2 and X2X1.

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

ueq01.gif

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, cacm6405_z.gif. 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 cacm6405_aa.gif. We denote the corresponding coloring as the stable coloring and define cacm6405_ab.gif. As an example, the sequence of colorings for a path of length 6 is depicted in Figure 2.

f2.jpg
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) XG. 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 ϕ: GH between two graphs G and H satisfies that χG(v) = χH for all vV (G). The color refinement algorithm distinguishes G and H if there exists a color c such that

ueq02.gif

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 GH. Note that

ueq03.gif

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 cacm6405_ac.gif computed by k-WL determines for each ῡ∈Vk the isomorphism-type of the underlying ordered induced subgraph. More precisely, cacm6405_ad.gif if for all i, j ∈ [k] it holds vi = vj if and only if wi = wj, and vivjE if and only if wiwjE. The initial coloring is refined by iteratively computing colorings cacm6405_ae.gif for i > 0. For ῡ=(v1,…,vk) and wV, let ῡ[i/w]:=(v1,…,vi−1,w,vi+1,…,vk) be the tuple obtained from by replacing the i-th entry with vertex w. Now we define cacm6405_af.gif where

ueq04.gif

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

As an example, the coloring XG,2 where G is a cycle of length 9 is depicted in Figure 3.

f3.jpg
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, wV (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) XG,k.

THEOREM 5 (Immerman and Lander17). Let G be a graph. Then, an isomorphism-invariant coloring that is equivalent to XG,k can be computed in time O(nk+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)−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 Gk H, if they are not distinguished by k-WL. A graph G is identified by k-WL if Gk H if and only if GH 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 kN. For graphs G, H on the same number of vertices, we define the bijective k-pebble game BPk (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 cacm6405_aj.gif with V(G) and cacm6405_ak.gif 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 cacm6405_al.gif. 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 cacm6405_am.gif where ῡ\i:=(v1,…,vi−1,vi+1,…,v) (and cacm6405_an.gif 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 vV (G) and sets w := f(v).
  • The new position is ((v1,…,v,v), (w1,…,w,w)).
  • Spoiler wins the play if for the current position cacm6405_ao.gif the induced graphs are not isomorphic. More precisely, Spoiler wins if there are i, j ∈[] such that vi=vjwi=wj or vivjE(G) ⇎ wiwjE(H). If the play never ends, Duplicator wins.

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

Moreover, for positions cacm6405_ap.gif Spoiler (resp. Duplicator) wins the game BPk (G, H) from position cacm6405_aq.gif if Spoiler (resp. Duplicator) has a winning strategy in the game BPk(G, H) starting from initial position cacm6405_ar.gif.

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 cacm6405_as.gif. Then cacm6405_at.gif if and only if Duplicator wins the pebble game BPk+1 (G, H) from the position cacm6405_au.gif.

COROLLARY 7. Let G, H be two graphs. Then Gk H if and only if Duplicator wins the pebble game BPk+1 (G, H).

Back to Top

3. Rank Width

Rank width is a graph invariant that was first introduced by Oum and Seymour21 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 F2.

Let G be a graph. For X, YV (G), we define cacm6405_av.gif where (M(X, Y))x,y = 1 if and only if xyE(G). Furthermore, cacm6405_aw.gif where cacm6405_ax.gif and rk2(A) denotes the F2-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) → 2V(G) such that

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

(R.2) γ(t)=γ(t1)∪ γ(t2) and γ(t1)∩ γ(t2)=/ for all internal nodes tV(T) with children t1 and t2, and

(R.3) |γ(t)| = 1 for all tL (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

ueq05.gif

The rank width of a graph G is

ueq06.gif

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

f4.jpg
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 width5 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 ij, 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 ρij (G, lab := (G, lab') where cacm6405_ay.gif.
  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

ueq07.gif

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

eq01.gif

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 Kn has rank width rw(Kn) = 1 and tree width tw(Kn) = 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 BP3k+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 XGV(G) and XHV(H) and vertices cacm6405_az.gif and cacm6405_ba.gif where pk such that there is no isomorphism ϕ: G[XG] → H[XH] with cacm6405_bb.gif and cacm6405_bc.gif (where G[XG] and H[XH] denote the induced subgraphs on vertex sets XG and XH). By gradually decreasing the size of the set XG, Spoiler eventually wins the game since, as soon as |XG| ≤ 2k + 1, the entire set XG can be pebbled.

During the play, the set XG essentially corresponds to the sets γ(t) where tV(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 XG. Initially, XG := V(G), XH =: 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 t1, t2 of t in the rank decomposition (T, γ). To maintain the invariant described above, it is necessary to "split" γ(t1) from γ(t2) 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 XV(G). For v, wX, we define vX w if cacm6405_bd.gif. For vX, we define the vector cacm6405_be.gif where av,w = 1 if and only if vwE(G). Note that vX w if and only if vecx (v) = vecx (w). Moreover, for AX, we define vecx (A) = {venX (v)|vA}.

For any set of vectors cacm6405_bf.gif, we denote by 〈S〉 the linear space spanned by S. A set cacm6405_bg.gif is a linear basis forS〉 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. AX and cacm6405_bh.gif,
  2. vecx (A) forms a linear basis for 〈venx (X)〉, and
  3. cacm6405_bi.gif forms a linear basis for cacm6405_bj.gif.

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 cacm6405_bk.gif. 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 cacm6405_bl.gif such that ({a1, …, ap}, {b1,…,bp}) is a split pair for X.

Now the central claim for split pairs is that pebbling an ordered split pair cacm6405_bm.gif 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 cacm6405_bn.gif to be the coloring computed by the color refinement algorithm on the graph G where all vertices a1, …, ap, b1, …, bp 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 cacm6405_bo.gif.

Definition 2. Let G = (V, E) be a graph and X VC 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 Gf = (V, Ef) where

ueq08.gif

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) ⊆ 2V(G) be the set of vertex sets of the connected components of Gf. Observe that Comp(G, f) forms a partition of the vertex set of G.

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

Then there is a flip function f for the graph G with coloring cacm6405_bo.gif such that for every C ∈ Comp(G, f) it holds that CX or cacm6405_bq.gif.

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

f5.jpg
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 cacm6405_bo.gif 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 Gf and Hf instead of G and H. For Gf and Hf, Spoiler can now restrict the game to a pair of connected components of the two graphs XGV(G) and XHV(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 γ(t1) and γ(t2) 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 XG and XH are only assured to be nonisomorphic as long as cacm6405_br.gif as well as cacm6405_bs.gif 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, X1, X2V(G) such that X = X1X2 and X1X2 = /. Let (A, B) be a split pair of X and let (Ai, Bi) be split pairs for Xi, i ∈ {1, 2}. We say that (Ai, Bi), i ∈ {1, 2}, are nice (with respect to (A, B)) if

  1. AXiAi, and
  2. B3−iXiAi 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 XG or XH. The following lemma guarantees the existence of nice triples of split pairs.

LEMMA 10. Let G be a graph and X, X1, X2V(G) such that X = X1X2 and X1X2 = /. Let (A, B) be a split pair of X. Then there are nice split pairs (Ai, Bi) for Xi 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 theorem7 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 paper3 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 Flum6).

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 PC.

Although there are good reasons to define an abstract logic capturing PTIME this way (see Gurevich13), 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

ueq09.gif

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):

ueq10.gif

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+C2—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, Immerman15 and independently Vardi22 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 (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.10

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 nO(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)nc 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

References

1. Babai, L. Graph isomorphism in quasipolynomial time [extended abstract]. In Proceedings of the 48th 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, 2nd 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 56th 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 14th 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

Back to Top

Authors

Martin Grohe ([email protected]), RWTH Aachen University, Aachen, Germany.

Daniel Neuen ([email protected]), RWTH Aachen University, Aachen, Germany.

Back to Top

Footnotes

A previous version of this paper, entitled "Canonisation and Definability for Graphs of Bounded Rank Width" was published in Proceedings of the 34th 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 [email protected]

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


 

No entries found