arXiv:1705.03283v1 [cs.CC] 9 May 2017

An exponential lower bound for Individualization-Refinement
algorithms for Graph Isomorphism
Daniel Neuen and Pascal Schweitzer
RWTH Aachen University
{neuen,schweitzer}@informatik.rwth-aachen.de
May 10, 2017
Abstract
The individualization-refinement paradigm provides a strong toolbox for testing isomorphism
of two graphs and indeed, the currently fastest implementations of isomorphism solvers all follow
this approach. While these solvers are fast in practice, from a theoretical point of view, no general
lower bounds concerning the worst case complexity of these tools are known. In fact, it is an
open question whether individualization-refinement algorithms can achieve upper bounds on the
running time similar to the more theoretical techniques based on a group theoretic approach.
In this work we give a negative answer to this question and construct a family of graphs on
which algorithms based on the individualization-refinement paradigm require exponential time.
Contrary to a previous construction of Miyazaki, that only applies to a specific implementation
within the individualization-refinement framework, our construction is immune to changing the
cell selector, or adding various heuristic invariants to the algorithm. Furthermore, our graphs
also provide exponential lower bounds in the case when the k-dimensional Weisfeiler-Leman
algorithm is used to replace the standard color refinement operator and the arguments even
work when the entire automorphism group of the inputs is initially provided to the algorithm.

1

Introduction

The individualization-refinement paradigm provides a strong toolbox for testing isomorphism of two
graphs. To date, algorithms that implement the individualization-refinement paradigm constitute
the fastest practical algorithms for the graph isomorphism problem and for the task of canonically
labeling combinatorial objects.
Originally exploited by McKay’s software package nauty [14] as early as 1981, in a nutshell,
the basic principle is to classify vertices using a refinement operator according to an isomorphisminvariant property. In a basic form one usually uses the so-called color refinement operator, also
called 1-dimensional Weisfeiler-Leman algorithm, for this purpose. Whenever the refinement is
not sufficient, vertices within a selected color class (usually called a cell) are individualized one by
one in a backtracking manner as to artificially distinguish them from other vertices. This yields
a backtracking tree, that is traversed to explore the structure of the input graphs. Additional
pruning with the use of invariants and the exploitation of automorphisms of the graphs makes the
approach viable in practice, leading to the fastest isomorphism solvers currently available. The use
of invariants also allows us to define a smallest leaf, which can be used to canonically label the
graph, i.e., to rearrange the vertices in canonical fashion as to obtain a standard copy of the graph.
1

There are several highly efficient isomorphism software packages implementing the paradigm.
Among them are nauty/traces [15], bliss [11], conauto [13] and saucy [6]. While they all follow the
basic individualization-refinement paradigm, these algorithms differ drastically in design principles
and algorithmic realization. In particular, they differ in the way the search tree is traversed, they use
different low level subroutines, have diverse ways to perform tasks such as automorphism detection,
and they use different cell selection strategies as well as vertex invariants and refinement operators.
With Babai’s [2] recent quasi-polynomial time algorithm for the graph isomorphism problem, the
theoretical worst case complexity of√algorithms for the graph isomorphism problem was drastically
c
improved from a previous best eO( n log n) (see [3]) to O(nlog n ) for some constant c ∈ N. As an
open question, Babai asks [2] for the worst case complexity of algorithms based on individualizationrefinement techniques. About this worst case complexity, very little had been known.
In 1995 Miyazaki [16] constructed a family of graphs on which the then current implementation
of nauty has exponential running time. For this purpose these graphs are designed to specifically fool the cell selection process into exponential behavior. However, as Miyazaki also argues,
with a different cell selection strategy the examples can be solved in polynomial time within the
individualization-refinement paradigm.
In this paper we provide general lower bounds for individualization-refinement algorithms with
arbitrary combinations of cell selection, refinement operators, invariants and even given perfect
automorphism pruning. More precisely, the graphs we provide yield an exponential size search tree
(i.e., 2Ω(n) nodes) for any combination of refinement operator, invariants, and the cell selector which
are not stronger than the k-dimensional Weisfeiler-Leman algorithm for some fixed dimension k.
The natural class of algorithms for which we thus obtain lower bounds encompasses all software
packages mentioned above even with various combinations of switches that can be turned on and off
in the execution of the algorithm to tune the algorithms towards specific input graphs. Our graphs
are asymmetric, i.e., have no non-trivial automorphisms, and thus no strategy for automorphism
detection can help the algorithm to circumvent the exponential lower bound.
Our construction makes use of a construction of Cai-Fürer-Immerman [4] and the multipede
construction of Gurevich and Shelah [9] that yields for every dimension k non-isomorphic finite
rigid structures that are not distinguishable by the k-dimensional Weisfeiler-Leman algorithm. In
more detail, our construction starts with a bipartite base graph that is obtained by a simple random
process. With high probability such a graph has strong expansion properties ensuring a variant of the
meagerness property of [9] suitable for our purposes. Additionally, with high probability the graph
has an almost-disjointness property for neighborhoods of vertices from one bipartition class. To the
base graph we apply a bipartite variant of the construction of [4]. By individualizing a small fraction
of vertices, we can guarantee that the final graphs are rigid (have no non-trivial automorphisms).
For our theoretical analysis, we define a closure operator that gives us control over the effect of the
Weifeiler-Leman algorithm on the graphs. Due to the disjointness property this effect is limited.
Exploiting automorphism of subgraphs of the input, we then proceed to argue that there is an
exponential number of colorings of the graph that cannot be distinguished. These statements can
be combined to show that the search tree of every algorithm within the individualization-refinement
framework has exponential size.
Some of the packages above have a mechanism called component recursion (see [12]). We show
that even this strategy cannot yield improvements for our examples. We should point out that
component recursion was used in Goldberg’s result [8] which shows that with the right cell selection strategy and the use of component recursion (in that paper called sections) individualization-

2

refinement algorithms have exponential upper bounds, matching our lower bounds.
We also should remark that, seen as colored graphs, our graphs have bounded color class size and
as such isomorphism of the graphs can be decided in polynomial time using simple group theoretic
techniques (see [1, 7]).
Since the software packages that follow the individualization-refinement paradigm are designed
for practical purposes rather than to obtain theoretical worst case guarantees, the question lies
at hand how meaningful the lower bounds provided in the paper are. However, in separate work
[18], we investigate practical benchmark graphs. It turns out that constructions related to the ones
discussed in this paper in fact yield graphs which, experimentally, pose by far the most challenging
graph isomorphism instances available to date.

2
2.1

Preliminaries
Graphs

A graph is a pair G = (V, E) with vertex set V = V (G) and edge relation E = E(G). In this paper
all graphs are finite simple,Sundirected graphs. The neighborhood of v ∈ V (G) is denoted N (v). For
a set X ⊆ V let N (X) = ( v∈X N (v)) \ X.
An isomorphism from a graph G to another graph H is a bijective mapping ϕ : V (G) → V (H)
which preserves the edge relation, that is {v, w} ∈ E(G) if and only if {ϕ(v), ϕ(w)} ∈ E(H) for
all v, w ∈ V (G). Two graphs G and H are isomorphic (G ∼
= H) if there is an isomorphism from G
ϕ
∼
to H. We write G = H to indicate that ϕ is an isomorphism from G to H. The isomorphism type of
a graph G is the class of graphs isomorphic to G. An automorphism of a graph G is an isomorphism
from G to itself. By Aut(G) we denote the group of automorphisms of G. A graph G is rigid (or
asymmetric) if its automorphism group Aut(G) is trivial, that is, the only automorphism of G is
the identity map.
A vertex coloring of a graph G is a map c : V (G) → C into some set of colors C. Mostly, we will
use vertex colorings into the natural numbers c : V (G) → {1, . . . , n} =: [n].
Isomorphisms between two colored graphs (G, c) and (G′ , c′ ) are required to preserve vertex
colors. Slightly abusing notation we will sometimes not differentiate between G and (G, c), if the
coloring is apparent from context.
We will also consider vertex colored graphs with a distinguished sequence of not necessarily distinct vertices (G, c, v̄), where v̄ ∈ V ℓ for some ℓ ∈ N. For a tuple v̄ ∈ V ℓ we let |v̄| = ℓ be the length of
the tuple. Two such graphs with distinguished sequences (G, c, (v1 , . . . , vt )) and (G′ , c′ , (v1′ , . . . , vt′ ′ ))
are isomorphic if t = t′ and there is an isomorphism ϕ from G to G′ preserving vertex colors and satisϕ
fying ϕ(vi ) = v ′ for all i ∈ {1, . . . , t}. In analogy to the definition above we write (G, c, (v1 , . . . , vt )) ∼
=
i

(G′ , c′ , (v1′ , . . . , vt′ ′ )).

2.2

The Weisfeiler-Leman algorithm

The k-dimensional Weisfeiler-Leman algorithm is a procedure that, given a graph G and a coloring of the k-tuples of the vertices, computes an isomorphism-invariant refinement of the coloring.
Let χ, χ′ : V k → C be colorings of the k-tuples of vertices of G, where C is some set of colors. We
say χ refines χ′ (χ  χ′ ) if for all v̄, w̄ ∈ V k we have
χ(v̄) = χ(w̄) ⇒ χ′ (v̄) = χ′ (w̄).
3

Let (G, c) be a colored graph (where c : V (G) → {1, . . . , n} is a coloring of the vertices) and let
k
k ≥ 1 be some integer. We set χG
0 : V → C to be the coloring, where each k-tuple is colored by the
isomorphism type of its underlying induced ordered subgraph. More precisely, we define χG
0 in such
G (w , . . . , w ) if and only if for all i ∈ {1, . . . , k} it holds that c(v ) =
(v
,
.
.
.
,
v
)
=
χ
a way that χG
1
i
1
k
k
0
0
c(wi ) and for all i, j ∈ {1, . . . , k} we have vi = vj ⇔ wi = wj and {vi , vj } ∈ E(G) ⇔ {wi , wj } ∈
G
E(G). For k > 1 we recursively define for G the coloring χG
i+1 by setting χi+1 (v1 , . . . , vk ) :=
(χG
i (v1 , . . . , vk ); M), where M is the multiset defined as
 G

G
χi (w, v2 , . . . , vk ), χG
i (v1 , w, . . . , vk ), . . . , χi (v1 , . . . , vk−1 , w) | w ∈ V .

For k = 1 the definition is analogous but the multiset is defined as M := {{χG
i (w) | w ∈ N (v1 )}}
i.e., iterating only over neighbors of v1 .
By definition, every coloring χG
i+1 induces a refinement of the partition of the k-tuples of the
graph G with coloring χG
.
Thus,
there is some minimal i such that the partition induced by the
i
G
coloring χi+1 is not strictly finer than the one induced by the coloring χG
i on G. For this minimal i,
G.
we call the coloring χG
the
stable
coloring
of
G
and
denote
it
by
χ
i
For k ∈ N, the k-dimensional Weisfeiler-Leman algorithm takes as input a colored graph (G, c)
and returns the colored graph (G, χG ). For two colored graphs (G, c) and (G′ , c′ ), we say that
the k-dimensional Weisfeiler-Leman algorithm distinguishes G and G′ with respect to the initial
colorings c and c′ if there is some color C such that the sets {v̄ | v̄ ∈ V k (G), χG (v̄) = C} and
′
{w̄ | w̄ ∈ V k (G′ ), χG (w̄) = C} have different cardinalities. We write G ≃k H if the k-dimensional
Weisfeiler-Leman algorithm does not distinguish between G and H.
We extend the definition to vertex-colored graphs with distinguished vertices. Let G and H
be graphs with vertex colorings cG and cH and let (x1 , . . . , xt ) ∈ V (G)t and (y1 , . . . , yt ) ∈ V (H)t
be sequences of vertices. Define cc
c
G as the coloring given by c
G (v) = (cG (v); {i ∈ {1, . . . , t} |
v = xi }). We call this the coloring obtained from cG by individualizing (x1 , . . . , xt ). Similarly
we define cc
H as (cH (v); {i ∈ {1, . . . , t} | v = yi }). Then we say that (G, cG , (x1 , . . . , xt )) is not
distinguished from (H, cH , (y1 , . . . , yt )), in symbols (G, cG , (x1 , . . . , xt )) ≃k (H, cH , (y1 , . . . , yt )), if G
and H are not distinguished by the k-dimensional Weisfeiler-Leman algorithm with respect to the
initial colorings cc
G and cc
H . We denote by WLk (G, c, v̄) the vertex coloring that is induced by the
G
stable coloring with respect to the initial coloring cc
G , that is, (WLk (G, c, v̄))(w) = χ (w, . . . , w)
G
where χ is the stable coloring of the k-tuples with respect to the initial coloring cc
G.
There is a close connection between the Weisfeiler-Leman algorithm and fixed-point logic with
counting. In fact the stable coloring computed by k-dimensional Weisfeiler-Leman comprehensively
captures the information that can be obtained in fixed-point logic with counting using at most k + 1
variables. We refer to [4, 10] for more details.

Pebble Games. We will not require details about the information computed by the WeisfeilerLeman algorithm and rather use the following pebble game that is known to capture the same
information. Let k ∈ N be a fixed number. For graphs G, H on the same number of vertices and
with vertex colorings cG and cH , respectively, we define the bijective k-pebble game on G and 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 (v̄, w̄) with v̄ ∈
(V (G) ∪ {⊥})k and w̄ ∈ (V (G) ∪ {⊥})k .
4

• The initial position of the game is ((⊥, . . . , ⊥), (⊥, . . . , ⊥)).
• Each round consists of the following steps. Suppose the current position of the game is
((v1 , . . . , vk ), (w1 , . . . , wk )).
(S) Spoiler chooses some i ∈ [k].
(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 then the pair consisting of v̄ ′ = (v1 , . . . , vi−1 , v, vi−1 , . . . , vk ) and w̄′ =
(w1 , . . . , wi−1 , w, wi−1 , . . . , wk ).
• Spoiler wins the game if for the current position ((v1 , . . . , vk ), (w1 , . . . , wk )) the induced graphs
are not isomorphic. More precisely, Spoiler wins if there is an i ∈ {1, . . . , k} such that vi =
⊥⇔
/ wi = ⊥ or cG (vi ) 6= cH (wi ) or there are i, j ∈ {1, . . . , k} such that vi = vj ⇔
/ wi = wj
or {vi , vj } ∈ E(G) ⇔
/ {wi , wj } ∈ E(H). If the play never ends Duplicator wins.
We say that Spoiler (respectively Duplicator) wins the bijective k-pebble game BPk (G, H) if
Spoiler (respectively Duplicator) has a winning strategy for the game.
Theorem 2.1 (cf. [4, 10]). Let G, H be two graphs. Then G ≃k H if and only if Duplicator wins
the pebble game BPk+1 (G, H).

3

Individualization-refinement algorithms

An extensive description of the paradigm of individualization-refinement algorithms is given in [15].
These algorithms capture information about the structure of a graph by coloring the vertices. An
initially uniform coloring is first refined in an isomorphism-invariant manner as follows.
A refinement operator is an isomorphism-invariant function ref that takes a graph G, a coloring c
and a sequence v̄ = (v1 , . . . , vℓ ) ∈ V ℓ and outputs a coloring ref(G, c, v̄)  c such that vi has a
ϕ
unique color for every i ∈ [ℓ]. In this context isomorphism-invariant means that (G, c, v̄) ∼
= (G′ , c′ , v̄ ′ )
ϕ

implies (G, ref(G, c, v̄)) ∼
= (G′ , ref(G′ , c′ , v̄ ′ )). A typical choice for such a refinement would be the
1-dimensional Weisfeiler-Leman algorithm described above, where the vertices in v̄ are artificially
given special colors.
A vertex with a unique color is called a singleton and a coloring is called discrete if all vertices
are singletons. Due to the isomorphism-invariance, every isomorphism must preserve the refined
colors. Thus, in case the refinement operator produces a discrete coloring on a graph G, it is trivial
to check whether this graph is isomorphic to another graph G′ . Indeed, the refinement of G′ must
also be discrete and there is at most one color preserving bijection between the vertex sets which can
be trivially checked for being an isomorphism. However, if the coloring of G is not discrete we need
to do more work. In this case we select a color class, usually called a cell, and then individualize
a single vertex from the class. Here individualization means to refine the coloring by making the
vertex a singleton. Since such an operation is not necessarily isomorphism-invariant, we branch
over all choices of this vertex within the chosen cell. To the coloring with the newly individualized
vertex, we apply the refinement operator again and proceed in a recursive fashion. To explain this
in more detail we first need to clarify how the cell is chosen.
5

Let G = (V, E) be a graph and c : V (G) → [n] be a coloring of the vertices. A cell selector is
an isomorphism-invariant function sel which takes as input a graph G and a coloring c and either
outputs sel(G, c) ∈ [n] with |c−1 (sel(G, c))| ≥ 2 if such a color exists or sel(G, c) =⊥ otherwise.
In this context isomorphism-invariant means that (G, c) ∼
= (G′ , c′ ) implies sel(G, c) = sel(G′ , c′ ).
The performance of an individualization-refinement algorithm can drastically depend on the cell
selection strategy. A typical strategy would be to take the first class of smallest size.
Let G = (V, E) be a graph with an initial coloring c0 : V (G) → [n]. Let sel be a cell selector
and ref a refinement operator. Inductively define the search tree T ref,sel (G, c0 ) as follows. The
root of the tree is labeled with the empty sequence ε. Let v̄ = (v1 , . . . , vℓ ) be a node of the search
tree. Let c = ref(G, c0 , v̄) be the coloring computed by the refinement operator for the current
sequence and let i = sel(G, c) be the color selected by the cell selector. If i =⊥ then v̄ is a leaf of
the search tree and the coloring c is discrete. Otherwise, for each w ∈ c−1 (i), there is child node
labeled with (v1 , . . . , vℓ , w). The vertices of the search tree are referred to as nodes and we identify
them with the sequence of vertices they are labeled with.
Pruning with invariants. Together a cell selector and a refinement operator are sufficient to
build a correct isomorphism test. Indeed, two graphs are isomorphic if and only if they have isomorphic leaves in their search tree. For these leaves, due to having a discrete coloring, isomorphism
is trivial to check. However, there are two further ingredients that are crucial for the efficiency
of practical individualization-refinement algorithms. These are the use of node invariants and the
exploitation of automorphisms. Let Ω be a totally ordered set. A node invariant is an isomorphisminvariant function inv taking a graph G, a coloring c and a sequence v̄ = (v1 , . . . , vℓ ) ∈ V ℓ and
outputs an element inv(G, c, v̄) ∈ Ω such that for all vertex sequences v̄, v̄ ′ ∈ V ∗ of equal length ℓ
(i) if inv(G, c, (v1 , . . . , vℓ )) < inv(G, c, (v1′ , . . . , vℓ′ )) then it also holds for all w, w′ ∈ V that
inv(G, c, (v1 , . . . , vℓ , w)) < inv(G, c, (v1′ , . . . , vℓ′ , w′ )) and
(ii) if ref(G, c, v̄) and ref(G, c, v̄ ′ ) are discrete and inv(G, c, v̄) = inv(G, c, v̄ ′ ) then (G, c, v̄) ∼
=
(G, c, v̄ ′ ).
Here isomorphism-invariant means that (G, c, v̄) ∼
= (G′ , c′ , v̄ ′ ) implies inv(G, c, v̄) = inv(G′ , c′ , v̄ ′ ).
Let inv be a node invariant and define

I = {v̄ ∈ V (T ref,sel (G, c0 )) | ∄ v̄ ′ ∈ V (T ref,sel (G, c0 )) : |v̄| = |v̄ ′ | ∧ inv(G, c0 , v̄ ′ ) < inv(G, c0 , v̄) }.

ref,sel
Finally, define the search tree Tinv
(G, c0 ) := T ref,sel (G, c0 )[I] as the subtree induced by the
ref,sel
node set I. Observe that Property (i) implies that Tinv
(G, c0 ) is indeed a tree. By using the
invariant we thus cut off the parts of the search tree that do not have a nodes that are minimal
among all nodes on their level. However, due to isomorphism invariance, the property that two
graphs are isomorphic if and only if they have isomorphic leaves remains.
The use of an invariant also makes it easy to define a canonical labeling using a leaf for which
the invariant is smallest. For the purpose of obtaining our lower bounds we will not require detailed
information on the concept of a canonical labeling and rather refer to [15].

Pruning with automorphisms. The second essential ingredient needed for the practicality of
individualization-refinement algorithms is the exploitation of automorphisms. Indeed, if for two
ref,sel
nodes in Tinv
(G), labeled with v̄ and v̄ ′ , respectively, we have (G, c, v̄) ∼
= (G′ , c′ , v̄ ′ ) then it is
6

sufficient to explore only one of the subtrees corresponding to the two nodes (we refer to [15] for
correctness arguments). Thus automorphisms that are detected by the algorithm can be used to
cut off further parts of the search tree. An efficient strategy for the detection of automorphisms
is an essential part of individualization-refinement algorithms and here the various packages differ
drastically (see [15]). Making our lower bounds only stronger, in this paper we take the following
standpoint. We will assume that all automorphisms of the input graph are provided to the algorithm
in the beginning at no cost. In fact the following lower bound will be sufficient for our purposes.
Proposition 3.1. The running time of an individualization-refinement algorithm with cell selector sel, refinement operator ref and invariant inv on a graph G is bounded from below
ref,sel
by |Tinv
(G)|/| Aut(G)|.
The program nauty has an extensive selection of refinement operators/invariants that can be
activated via switches. To name a couple, there are various options to count for each vertex the
number of vertices reachable by paths with vertex colors of a certain type, options to count substructures such as triangles, quadrangles, cliques up to size 10, independent sets up to size 10, and
even options to count the number of Fano planes (the projective plane with 7 points and 7 lines).
Finally, the user can implement their own invariant via a provided interface.
Our goal is to make a comprehensive statement about individualization-refinement algorithms
independent of the choices for sel, ref, and inv. However, there is an intrinsic limitation here.
For example a complete invariant that can distinguish any two non-isomorphic graphs would yield
a polynomial-size search tree. Likewise would a refinement operator that refines every coloring into
the orbit partition under the automorphism group. However, we do not know how to compute these
two examples efficiently. In fact computing either of these is at least as hard as the isomorphism
problem itself.
Of course it is nonsensical to allow that an individualization-refinement algorithm uses a subroutine that already solves the graph isomorphism problem. It becomes apparent that there is a
limitation to the operators we can allow. However, within this limitation we strive to be as general
as possible. With this in mind, throughout this paper we require that the information computed
by refinement operators, invariants and cell selectors can be captured by a fixed dimension of the
Weisfeiler-Leman algorithm. This is the case for all available choices in all the practical algorithms.
In what follows, we describe the requirement more formally.
We say a cell selector sel is k-realizable if sel(G, c, v̄) = sel(G′ , c′ , v̄ ′ ) whenever (G, c, v̄) ≃k
(G′ , c′ , v̄ ′ ). Similarly a node invariant is k-realizable if inv(G, c, v̄) = inv(G′ , c′ , v̄ ′ ) whenever
(G, c, v̄) ≃k (G′ , c′ , v̄ ′ ). Intuitively this means that whenever the k-dimensional Weisfeiler-Leman
algorithm cannot distinguish between the graphs associated with two nodes of the refinement tree
then the cell selector and the node invariant have to behave in the same way on both nodes. Finally
a refinement operator is k-realizable if WLk (G, c, v̄)  ref(G, c, v̄) holds for all triples (G, c, v̄).
We want to stress the fact that all the operators used in all practical implementations (e.g.
nauty/traces, bliss, conauto, etc.) are k-realizable for some small constant k ∈ N. In fact, from a
theoretical point of view it would always be better to directly use the Weisfeiler-Leman algorithm as
a refinement operator, since it is polynomial-time computable. Let us remark that the only reason
why the individualization-refinement algorithms do not do this is the excessive running time and
space consumption.
Based on these definitions we can now formulate our main result, which implies an exponential
lower bound for individualization-refinement algorithms within the framework.
7

Theorem 3.2. For every constant k ∈ N there is a family of rigid graphs (Gn )n∈N with |V (Gn )| ≤ n
such that for every k-realizable cell selector sel, every k-realizable refinement operator ref, and
every k-realizable node invariant inv it holds that
ref,sel
|Tinv
(Gn )| ∈ 2Ω(n) .

(3.1)

Together with Proposition 3.1 this implies exponential lower bounds on the running time of
individualization-refinement algorithms.
For the theorem we construct graphs which have large search trees. To prove that these search
trees are large, we use the following lemma stating that for every two tuples v̄, w̄ ∈ V ℓ for which
(G, v̄) ≃k (G, w̄) holds, either both tuples are nodes in the search or neither of them is.
Lemma 3.3. Suppose k ∈ N and let sel be a k-realizable cell selector, inv a k-realizable node
invariant and ref a k-realizable refinement operator. Furthermore, let G be a graph and suppose
ref,sel
ref,sel
v̄ ∈ V (Tinv
(G)). Let m = |v̄|. Then w̄ ∈ V (Tinv
(G)) for every w̄ ∈ V (G)m with (G, v̄) ≃k
(G, w̄).
Proof. We prove the statement by induction on m ∈ N. For m = 0 the statement trivially holds
since v̄ = w̄ = ε. So suppose m > 0. Let v̄ ′ = (v̄1 , . . . , v̄m−1 ) be the tuple obtained from v̄ by
deleting the last entry and similarly define w̄′ = (w̄1 , . . . , w̄m−1 ). Clearly, (G, v̄ ′ ) ≃k (G, w̄′ ) and v̄ ′ ∈
ref,sel
ref,sel
V (Tinv
(G)). So by induction hypothesis it follows that w̄′ ∈ V (Tinv
(G)). Let c1 = ref(G, v̄ ′ )
′
and c2 = ref(G, w̄ ). Because sel and ref are k-realizable we get that sel(G, c1 ) = sel(G, c2 ) =:
−1
ref,sel (G)).
i. So v̄m ∈ c−1
1 (i) and also w̄m ∈ c2 (i) since (G, v̄) ≃k (G, w̄). Thus, w̄ ∈ V (T
ref,sel
Furthermore, inv(G, v̄) = inv(G, w̄) which implies that w̄ ∈ V (Tinv
(G)).
In the light of the lemma, to prove our lower bound it suffices to construct a graph G whose
search tree has a node v̄ with an exponential number of equivalent tuples. To argue the existence of
these we, roughly proceed in two steps. First, we show that to obtain a discrete partition we have
to individualize a linear number of vertices, in other words, we show that the search tree is of linear
height. Thus, there is a node v̄ in the corresponding search such that |v̄| is linear in the number of
vertices of G. Then, in a second step, we show that if |v̄| is sufficiently large, there are exponentially
many equivalent tuples. To find such equivalent tuples we prove a limitation of the effect of the
k-dimensional Weisfeiler-Leman algorithm after individualizing the vertices from v̄. Intuitively we
identify a subgraph containing v̄ which encapsulates the effect of the Weisfeiler-Leman algorithm.
We then exploit the existence of many automorphisms of this subgraph to demonstrate the existence
of many equivalent tuples.

4

The multipede construction

We describe a construction of a graph R(G) from a bipartite base graph G. The construction is a
combination of the Cai-Fürer-Immerman construction [4] giving graphs with large Weisfeiler-Leman
dimension and the construction of Gurevich and Shelah of multipedes [9] that yields rigid structures
with such properties.
The Cai-Fürer-Immerman gadget. For a non-empty finite set S we define the CFI gadget XS
to be the following graph. For each w ∈ S there are vertices aw and bw and for every A ⊆ S with
|A| even there is a vertex mA . For every A ⊆ S with |A| even there are edges {aw , mA } ∈ E(XS )
8

b3
m∅

a3
m{2,3}

b1
m{1,3}

a1
m{1,2}

b2
a2
Figure 4.1: Cai-Fürer-Immerman gadget X3
for all w ∈ A and {bw , mA } ∈ E(XS ) for all w ∈ S \ A. As an example the graph X3 := X[3] is
depicted in Figure 4.1. The graph is colored so that {aw , bw } forms a color class for each w and so
that {mA | A ⊆ S and |A| even} forms a color class.
Let X ⊆ S and γ ∈ Aut(XS ). We say that γ swaps exactly the pairs of X if γ(aw ) = bw for
w ∈ X and γ(aw ) = aw for w ∈ S \ X.
Lemma 4.1 ([4]). Let X ⊆ S. Then there is an automorphism γ ∈ Aut(XS ) swapping exactly the
pairs of X if and only if |X| is even. Additionally, if such an automorphism exists, it is unique.
The multipede graphs. Let G = (V, W, E) be a bipartite graph. We define the multipede graph
construction as follows. We replace every w ∈ W by twoSvertices a(w) and b(w). For each w ∈ W
let F (w) = {a(w), b(w)} and for X ⊆ W define F (X) = w∈X F (w). We then replace every v ∈ V
by the CFI gadget XN (v) and identify the vertices aw and bw with a(w) and b(w) for all w ∈ N (v).
The middle vertices will be denoted by mA (v) for A ⊆ N (v) with |A| even
S and the set of all middle
vertices of v ∈ V is denoted by M (v). For Y ⊆ V we define M (Y ) = v∈Y M (v). We also define
a vertex coloring for the graphs, however we only specify the color classes, since the actual names
of the colors will be irrelevant to us. In this manner, we require that for each w ∈ W , the pair of
vertices F (w) forms a color class, and for each v ∈ V the set of corresponding middle vertices M (v)
forms a color class. The resulting (vertex colored) graph will be denoted by R(G). An example of
this construction is shown in Figure 4.2.
For I ⊆ W we further define the graph RI (G) similar to R(G) but refine the coloring so that
for each w ∈ I both {a(w)} and {b(w)} form a color class. Hence, R(G) = R∅ (G).
Since we are aiming to construct rigid graphs we start by identifying properties of G that
correspond to R(G) having few automorphisms.
Definition 4.2. Let G = (V, W, E) be a bipartite graph. We say G is odd if for every ∅ =
6 X⊆W
there exists some v ∈ V such that |N (v) ∩ X| is odd.
Lemma 4.3. Let G = (V, W, E) be an odd bipartite graph. Then RI (G) is rigid for every I ⊆ W .
Proof. Let γ ∈ Aut(RI (G)) be an automorphism. Due to the coloring of the vertices, we know γ
stabilizes every set F (w) for w ∈ W and every set M (v) for v ∈ V .
9

w1

w2

w3

w4

w5

w6

W
G
V
v1

v2

v3

a(w1 ) b(w1 ) a(w2 ) b(w2 ) a(w3 ) b(w3 ) a(w4 ) b(w4 ) a(w5 ) b(w5 ) a(w6 ) b(w6 )

R(G)

Figure 4.2: The figure depicts a base graph G on the top and the graph R(G) obtained by applying
the multipede construction on the bottom.
Let X = {w ∈ W | γ(a(w)) = b(w)}. Suppose towards a contradiction that X 6= ∅. Since G is
odd there is some v ∈ V such that |N (v) ∩ X| is odd. Then γ restricts to an automorphism of the
gadget XN (v) swapping an odd number of the outer pairs. This contradicts the properties of CFI
gadgets (cf. Lemma 4.1).
So X = ∅ and thus γ(a(w)) = a(w) for all w ∈ W . From this it easily follows that γ is the
identity mapping.
For a bipartite graph G = (V, W, E) let AG ∈ FV2 ×W be the matrix with Av,w = 1 if and only if
{v, w} ∈ E(G). We denote by AT the transpose and by rk(A) the F2 -rank of a matrix A.
Lemma 4.4. Let G = (V, W, E) be a bipartite graph. Then | Aut(R(G))| = 2|W |−rk(AG ) .
Proof. For a matrix A ∈ Fm×n
we define the set Sol(A) = {x ∈ Fn2 | Ax = 0}. To show the lemma
2
it suffices to argue that | Aut(R(G))| = | Sol(AG )|.
For γ ∈ Aut(G) we define the vector xγ ∈ FW
2 by setting (xγ )w = 1 if and only if γ(a(w)) = b(w).
Observe that the mapping γ 7→ xγ is injective. Furthermore AG xγ = 0 since for each v ∈ V the
automorphism γ swaps an even number of neighbors of v.
For the backward direction let x ∈ Sol(AG ). Then, for each v ∈ V , the set {w ∈ N (v) | xw = 1}
has even cardinality. Thus, by the properties of the CFI-gadgets (cf. Lemma 4.1), there is a unique
automorphism γ ∈ Aut(R(G)) that swaps exactly those pairs (a(w), b(w)) for which xw = 1.
The arguments show that a bipartite graph G = (V, W, E) is odd if and only if rk(AG ) = |W |.
Corollary 4.5. Let G = (V, W, E) be an odd bipartite graph. Then there is some V ′ ⊆ V with
|V ′ | ≤ |W | such that the induced subgraph G[V ′ ∪ W ] is odd.
We can also use rk(AG ) to quantify how many vertices must be individualized to make G rigid.
Lemma 4.6. Let G = (V, W, E) be a bipartite graph. Then there is I ⊆ W with |I| ≤ |W |−rk(AG )
such that RI (G) is rigid.
10

W
Proof. Let B = {ew ∈ FW
2 | w ∈ W } be the standard basis for F2 (that is, (ew )u = 1 if and
only if w = u). Furthermore, for v ∈ V , let (AG )v be the v-th row of AG and let BI ⊆ B be a
minimal subset of B such that BI ∪ {((AG )v )T | v ∈ V } spans the entire space FW
2 . Finally, let
I = {w ∈ W | ew ∈ BI }. Clearly, |I| ≤ |W | − rk(AG ).
We argue that RI (G) is rigid. Let γ ∈ Aut(RI (G)) and let xγ ∈ FW
2 be the vector obtained by
setting (xγ )w = 1 if and only if γ(a(w)) = b(w). Then (ew )T xγ = 0 for all w ∈ I. Furthermore
(AG )v xγ = 0 for all v ∈ V by the same argument as in the proof of Lemma 4.4. Since BI ∪{((AG )v )T |
v ∈ V } spans the entire space FW
2 it follows by the standard linear algebra arguments that xγ = 0.
Thus γ is the identity.

5

The Weisfeiler-Leman refinement and the d-closure

We wish to understand the effect of the Weisfeiler-Leman refinement on graphs obtained with the
construction from the previous section. To this end we define the d-closure.
Definition 5.1. Let d ∈ N. For X ⊆ W define the d-attractor of X as
[
attrd (X) := X ∪
N (v).
v∈V : |N (v)\X|≤d

A set X ⊆ W is d-closed if X = attrd (X). The d-closure of X is the unique minimal superset which
is d-closed, that is
\
X ′.
cldG (X) =
X ′ ⊇X,
X ′ is d-closed

As observed in [9] the 1-closure describes exactly the information the 1-dimensional WeisfeilerLeman captures.
Lemma 5.2. Let G = (V, W, E) be a bipartite graph and suppose I ⊆ W . Then
(RI (G), a(w)) 6≃1 (RI (G), b(w)) ⇔ w ∈ cl1G (I)
for all w ∈ W .
Proof sketch. The backward direction follows by an inductive argument from the properties of the
CFI gadgets. For the forward direction it is easy to check that the corresponding partition on F (W )
directly extends to a stable partition for the graph RI (G).
Let G = (V, W, E) be a bipartite graph. Slightly abusing notation, for a set X ⊆ W define
N −1 (X) := {v ∈ V | N (v) ⊆ X}. For X ⊆ W define R(G)[[X]] := R(G)[F (X) ∪ M (N −1 (X))] (for
a graph G and a set X ⊆ V (G) the graph G[X] is the induced subgraph of G with vertex set X).
In this work we essentially argue that the previous lemma can be used to show that for a 1closed set X ⊆ W and a sequence of vertices x̄ = (x1 , . . . , xm ) from F (W ), for every automorphism
ϕ ∈ Aut(R(G)[[X]]) we have (R(G), x̄) ≃1 (R(G), ϕ(x̄)). The 1-closure thus gives us a method to
find tuples that cannot be distinguished by the 1-dimension Weisfeiler-Leman algorithm. However,
we require such a statement also for higher dimensions. Obtaining a similar statement characterizing
the effect of the k-dimensional Weisfeiler-Leman seems to be much more intricate and it is easy to
see that the d-closure does not achieve this. However, under some additional assumptions, we show
that the forward direction of the previous lemma still holds and thus, the d-closure gives us a tool
to control the effect of k-dimensional Weisfeiler-Leman which is sufficient for our purposes.
11

Lemma 5.3. Let k, d ∈ N and suppose d ≥ k. Let G = (V, W, E) be a bipartite graph and
X = {w1 , . . . , wm } ⊆ W be a d-closed set. Furthermore suppose that for distinct v, v1 , . . . , vk ∈ V
we have |N (v) ∩ (N (v1 ) ∪ N (v2 ) ∪ · · · ∪ N (vk ))| ≤ d − k. Let x̄ = (x1 , . . . , xm ) be a sequence of
vertices with xi ∈ F (wi ) and let ϕ ∈ Aut(R(G)[[X]]). Then (R(G), x̄) ≃k (R(G), ϕ(x̄)).
Proof. We prove that Duplicator has a winning strategy in the bijective (k + 1)-pebble game
BPk+1 ((R(G), x̄), (R(G), ϕ(x̄))) played on (R(G), x̄) and (R(G), ϕ(x̄)). Towards this end we say
a vertex v ∈ V (respectively w ∈ W ) is pebbled if there exists a ∈ M (v) (respectively a ∈ F (w))
which is pebbled. Furthermore we say that a vertex w ∈ W is fixed if there is some pebbled v ∈ V
with {v, w} ∈ E(G). For a tuple ā ∈ V (R(G))≤k of length at most k of pebbled vertices let
cl(ā) = F (X) ∪ M (N −1 (X)) ∪ {M (v) | v ∈ V : v is pebbled}
∪ {F (w) | w ∈ W : w is pebbled or fixed}.
Now let ℓ ≤ k, ā, b̄ ∈ V (R(G))ℓ and suppose there is an isomorphism α : cl(ā) → cl(b̄) from
R(G)[cl(ā)] to R(G)[cl(b̄)] mapping x̄ to ϕ(x̄) and ā to b̄. Observe that α extends ϕ and for ℓ = 0
we can choose α = ϕ.
Claim 1. For every unpebbled v ∈ V with N (v) * X there is some w ∈ N (v) \ X which is neither
pebbled nor fixed.
Proof. Consider N (v) \ X. Since X is d-closed we conclude that |N (v) \ X| ≥ d + 1. By the
assumption of the lemma there are at most d − k elements in N (v) that are fixed. Thus, N (v) \ X
contains at least k + 1 elements which are not fixed. Furthermore, there are at most k vertices
in N (v) that are pebbled. Thus there is at least one element that is neither pebbled nor fixed. y
For each unpebbled v ∈ V with N (v) * X choose a wv ∈ N (v) \ X that is neither pebbled nor
fixed. Furthermore let T = {w ∈ X | α(a(w)) = b(w)}. For every a ∈ M (V ) we define
(
A △ (T ∩ N (v))
if |T ∩ N (v)| even, and
Ba :=
A △ (T ∩ N (v)) △ {wv } otherwise,
where A ⊆ N (a) is the set with mA (v) = a and △ denotes
define the bijection


α(a)
f : V (R(G)) → V (R(G)) : a 7→ a


mBa (v)

the symmetric difference. We can now
if a ∈ cl(ā)
if a ∈ F (W ) \ cl(ā)
if a ∈ M (V ) \ cl(ā).

It is easy to check that for every a ∈ V (R(G)) there is an isomorphism α : cl(ā, a) → cl(b̄, f (a))
from R(G)[cl(ā, a)] to R(G)[cl(b̄, b)] mapping x̄ to ϕ(x̄) and (ā, a) to (b̄, b).

6

Meager graphs

Searching for graphs in which we have control over the size of the d-closure of a set we generalize
the notion of an ℓ-meager graph [9].
Definition 6.1. Let G = (V, W, E) be a bipartite graph and let 0 < α < 1. The graph G is
(ℓ, α)-meager if for every ∅ =
6 X ⊆ W with |X| ≤ ℓ it holds that |N −1 (X)| < α|X|.
12

Meager graphs have two properties that are advantageous for our course. The first property is
that for sufficiently small X ⊆ W the graph Aut(R(G)[[X]]) has many automorphisms.
Lemma 6.2. Let G = (V, W, E) be (ℓ, α)-meager and X ⊆ W with |X| ≤ ℓ. Then
| Aut(R(G)[[X]])| ≥ 2(1−α)|X| .
Proof. By Lemma 4.4 for X ⊆ W with |X| ≤ ℓ we have that
| Aut(R(G)[[X]])| ≥ 2|X|−|N

−1 (X)|

≥ 2(1−α)|X| .

The second property that is advantageous for us is that in a meager graph the size of the d-closure
of a set X is only by a constant factor larger than |X| itself.
Lemma 6.3. Suppose d ∈ N and dα < 1. Let G = (V, W, E) be (ℓ, α)-meager and suppose
1
∅=
6 X ⊆ W with |X| ≤ ℓ(1 − dα) − d + 1. Then | cldG (X)| < 1−dα
|X|.
Proof. Let X0 ( · · · ( Xm be a sequence of sets such that X0 = X and Xi+1 = Xi ∪ N (vi ) for some
vi ∈ V with |N (vi ) \ Xi | ≤ d and such that Xm is d-closed. Clearly, for every i ∈ [m] it holds that
α
α
|X| and set j = ⌈ 1−dα
|X|⌉. Then |Xj | ≤ |X| + dj ≤ ⌊ℓ(1 −
|N −1 (Xi )| ≥ i. Suppose that m ≥ 1−dα
α
dα)⌋−d+1+d⌈ 1−dα ℓ(1−dα)⌉ ≤ ⌊ℓ(1−dα)⌋−d+1+d⌈ℓα⌉ = ℓ+⌊−ℓdα⌋−d+1+⌈ℓdα⌉+d−1 = ℓ.
Hence the meagerness is applicable to Xj . We conclude j ≤ |N −1 (Xj )| < α|Xj | ≤ α(|X| + dj)
α
α
|X|⌉. But this contradicts the definition of j. So m < 1−dα
|X| and thus,
implying j < ⌈ 1−dα
1
| clG (X)| = |Xm | ≤ |X| + dm < 1−dα |X|.
We now concern ourselves with the existence of meager graphs. However, we require several
additional properties. Indeed, in the light of Lemma 5.3 we also want certain neighborhoods to
be almost disjoint. Moreover we want the graph R(G) to only have few automorphisms, which by
Lemma 4.6 translates into the matrix AG having large rank.
Theorem 6.4. There exists r0 ∈ N such that for every r ∈ N with r ≥ r0 and every sufficiently
n 3
, r -meager graph G = (V, W, E) with
large n ∈ N there is an 10r
1. |V | = |W | = n,

2. deg(v) = r for all v ∈ V ,
3. |N (v1 ) ∩ N (v2 )| < 3 for all distinct v1 , v2 ∈ V and
4. rk(AG ) ≥ (1 − 2−r )n.
Our proof of the theorem, which covers the rest of this section, makes use of the fact that
bipartite expander graphs are meager.
Definition 6.5. Let G = (V, W, E) be a bipartite graph with |V | ≥ |W |. We call G a (γ, β)-expander
if for every Y ⊆ V with |Y | ≤ γ|V | it holds that |N (Y )| ≥ β|Y |.
One method to obtain bipartite expanders is by considering the following random process. Let
10 ≤ r ∈ N be a fixed number. Given vertex sets V and W with r ≤ |W |/4 and |V | = |W | we
obtain a bipartite graph G = (V, W, E) by choosing independently and uniformly at random, for
every v ∈ V a set of r distinct neighbors in W . We refer to [19, Section 4] and [17, Chapter 5.3] for
more information on expanders, including variants of the following lemma.
13

1 r
10r , 2

Lemma 6.6. For r sufficiently large, Pr(G is a


-expander) ≥ 98 .

Proof. Let n = |V | = |W |. For Y ⊆ V and X ⊆ W let pY,X denote the probability that that
N (Y ) ⊆ X. Then


|X| r·|Y |
pY,X ≤
.
n
Furthermore let β =
using the inequality

r
1
and γ = 10r
.
2 
n
k,
≤
(ne/k)
k

p≤

Let p be the probability that G is not a (γ, β)-expander. Then,
we get
X

X

pY,X

Y ⊆V
X⊆W
|Y |≤γ·n |X|=⌊β|Y |⌋

≤

⌊γ·n⌋

X X

X

s=1 Y ⊆V
X⊆W
|Y |=s |X|=⌊β|Y |⌋

≤

⌊γ·n⌋ 

≤

⌊γ·n⌋ 

X

n
s

s=1

X
s=1



n
⌊βs⌋

ne s
s





ne
βs



|X|
n

βs
n

r·|Y |

r·s

β·s 

βs
n

r·s

"
#s
X  ne   ne β  βs r
=
s
βs
n
⌊γ·n⌋
s=1

=

s r−β−1 1+β r−β
e
β
n

s

γ r/2−1 e1+r/2 (r/2)r/2

is

⌊γ·n⌋ 

X
s=1

=

⌊γ·n⌋ 

X
s=1

≤

⌊γ·n⌋ h

X

s r/2−1 1+r/2
e
(r/2)r/2
n

s=1

s

.

Now let x = γ r/2−1 e1+r/2 (r/2)r/2 . If r is sufficiently large then x = (10r)1−r/2 e1+r/2 (r/2)r/2 =
10er(e/20)r/2 < 1/10 . It follows that
p≤

∞
X

xs =

s=1

x
1
≤ .
1−x
9

Theorem 6.7 (cf. [5, Theorem 1.1]). For n ≥ k let Sn,k = {v ∈ Fn2 | |{i ∈ [n] | vi = 1}| =
k}. Furthermore let A ∈ F2n×n be a random matrix where the rows are drawn uniformly and
independently from Sn,k . There is a K ∈ N such that for every fixed k ≥ K it holds that
lim Pr(rk(A) ≥ (1 − 2−k )n) = 1.

n→∞

14

Lemma 6.8. Asymptotically almost surely there are no distinct vertices v1 , v2 ∈ V such that
|N (v1 ) ∩ N (v2 )| ≥ 3.
Proof. Let p be the probability that
there are distinct
v1 , v2 ∈ V with |N (v1 ) ∩ N (v2 )| ≥ 3. Further
n 
more pick c3 > 0 such that r−3
≤ c3 · n−3 · nr for all n ∈ N. Then, for n = |V | = |W | sufficiently
large,
 r 
 r 
r−3 |W |
r−3 |W |−r
X
X
r−3
r−s
s
r−s
≤ |V |2
p ≤ |V |2
|W |
|W |
s=0

s=0

 r 
r
≤ |V |2 (r − 2)
c3 · |W |−3
⌊r/2⌋
c4
≤
|W |

r

for some constant c4 > 0.
Proof of Theorem 6.4. Let r be sufficiently large and let G = (V, W, E) be a random bipartite graph
as described above with |W |/4 ≥ r and n = |V | = |W |. By Lemma 6.8, Condition 3 is satisfied
that Condition 4 is satisfied asymptotically
asymptotically almost surely and Theorem 6.7 implies

n 3
, r -meager with
almost surely. So it remains to show G is 10r
 a positive probability. By Lemma
1 r
6.6, with probability at least 8/9, the graph G is a 10r , 2 -expander. Suppose there was an
n
for which N −1 (X) ≥ 3r · |X|. Then we could choose Y ⊆ N −1 (X)
∅ =
6 X ⊆ W with |X| ≤ 10r
n
with |Y | = 3r · |X| ≤ 10r
(assuming r ≥ 3). But then |X| ≥ |N (Y )| ≥ 2r · |Y | ≥ r2 · 3r · |X| > |X|
which is a contradiction.

7

Lower bounds for individualization-refinement algorithms

In the previous section we have proven the existence of meager graphs with various additional
properties. We show now that applying the multipede construction to such graphs yields examples
where the search tree of individualization-refinement algorithms is large.
Lemma 7.1. Let k, d ∈ N and suppose d ≥ k and dα < 1. Let G = (V, W, E) be (ℓ, α)-meager and
let X = {w1 , . . . , wm } ⊆ W be a subset of cardinality m ≤ (1 − dα)ℓ − d + 1. Furthermore suppose
that for all distinct v, v1 , . . . , vk ∈ V we have |N (v) ∩ (N (v1 ) ∪ N (v2 ) ∪ · · · ∪ N (vk ))| ≤ d − k. Let
x̄ = (x1 , . . . , xm ) be a sequence with xi ∈ F (wi ). Then
|{ȳ ∈ F (W )m | (R(G), x̄) ≃k (R(G), ȳ)}| ≥ 2

1−α(d+1)
m
1−dα

.

b = cld (X) be the d-closure of X. By Lemma 6.3 we get that |X|
b < 1 |X| ≤ ℓ.
Proof. Let X
G
1−dα
b = X ∪ {u1 , . . . , us } and let z̄ = (x1 , . . . , xm , z1 , . . . , zs ) be an extension of x̄ with
Suppose X
zi ∈ F (ui ). By Lemmas 5.3 and 6.2 we conclude that
b
|{ȳ ∈ F (W )m+s | (R(G), z̄) ≃k (R(G), ȳ)}| ≥ | Aut(R(G)[[X]])|
≥ 2(1−α)(m+s) .

Let A = {ȳ ∈ F (W )m+s | (R(G), z̄) ≃k (R(G), ȳ)} and for ā ∈ A let πm (ā) be the projection onto
the first m components. Clearly, for ā, b̄ ∈ A, it holds that (R(G), πm (ā)) ≃k (R(G), πm (b̄)). So
|{ȳ ∈ F (W )m | (R(G), x̄) ≃k (R(G), ȳ)}| ≥ |A| · 2−s ≥ 2(1−α)(m+s)−s = 2(1−α)m−αs .
15

Since s ≤ m −

1
1−dα m

=

dαm
1−dα

we conclude that
dα2 m

2(1−α)m−αs ≥ 2(1−α)m− 1−dα = 2

Theorem 7.2. Let k ∈ N, ℓ ≥ max{9r, 45s, 18k} and α ≤
graph with n = |V | = |W | such that

1−α(d+1)
m
1−dα

1
10k .

.

Suppose G = (V, W, E) is a bipartite

1. G is (ℓ, α)-meager,
2. deg(v) = r for all v ∈ V ,
3. |N (v1 ) ∩ N (v2 )| < 3 for all distinct v1 , v2 ∈ V and
4. n − rk(AG ) ≤ s.
Then there is a subset I ⊆ W with |I| ≤ s such that
1. RI (G) is rigid and
2. for every k-realizable cell selector sel, every k-realizable node invariant inv and every krealizable refinement operator ref it holds that
1

ref,sel
|Tinv
(RI (G))| ≥ 2 36 ·ℓ .

(7.1)

Proof. Set d := 3k. By Lemma 4.6 there is a set I ⊆ W of size |I| ≤ s such that RI (G) is rigid.
Suppose I = {w1 , . . . , ws }.
Claim 1. For distinct v, v1 , . . . , vk ∈ V we have |N (v) ∩ (N (v1 ) ∪ N (v2 ) ∪ · · · ∪ N (vk ))| ≤ d − k.
Proof. We have N (v) ∩ (N (v1 ) ∪ N (v2 ) ∪ · · · ∪ N (vk )) ≤ 2k ≤ d − k.

y

We choose an arbitrary linear order on the set of vertices in W . For a vertex mA (v) ∈ R(G)
define the projection Π(mA (v)) to be the sequence (x1 , . . . , x|N (mA (v))| ) of the vertices in N (mA (v))
ordered according to the linear order of W (observe that for each w ∈ N (v) either a(w) or b(w)
occurs in the sequence). We extend Π to V (R(G)) by defining for w ∈ W that Π(a(w)) = (a(w))
and Π(b(w)) = (b(w)).
[ as the concatenation of the
For a sequence x̄ = (x1 , . . . , xt ) of vertices of R(G) we define Π(x̄)
[ in which all duplicates are
sequences Π(x1 ), . . . , Π(xt ). We let Π(x̄) be the subsequence of Π(x̄)
removed starting from right. (I.e, for a sequence ȳ = (y1 , . . . , yt ) we inductively the sequence ρ(ȳ)
by setting ρ(ε) = ε and letting ρ(y1 , . . . , yt ) be equal to ρ(y1 , . . . , yt−1 ), if yi = yt for some i < t,
[
and is equal to the concatenation of ρ(y1 , . . . , yt−1 ) and yt , otherwise. Then Π(x̄) = ρ(Π(x̄)).)
Claim 2.

For every sequence x̄ of vertices of R(G) it holds that
|{ȳ | (RI (G), ȳ) ≃k (RI (G), x̄)}| ≥ |{z̄ | (RI (G), z̄) ≃k (RI (G), Π(x̄))}|
≥ 2−s · |{z̄ | (R(G), z̄) ≃k (R(G), Π(x̄))}|.

16

Proof. Observe first that the second inequality holds since there are only 2s color preserving permutations of F (I).
For the first inequality suppose for z̄ we have (RI (G), z̄) ≃k (RI (G), Π(x̄)) then we can find
a lift ȳ = (y1 , . . . , yi ) with Π(ȳ) = z̄ so that yj and xj have the same color for all j ∈ {1, . . . , i}.
For this lift we have (RI (G), ȳ) ≃k (RI (G), x̄). Since lifts of distinct sequences must be distinct we
conclude the claim.
y
3k
)ℓ − d + 1⌋ ≥ ⌊ 12 ℓ⌋ − d + 1 ≥ 31 ℓ and let c :=
Now let t = ⌊(1 − dα)ℓ − d + 1⌋ ≥ ⌊(1 − 10k

1−α(3k+1)
1−3kα

1−α(d+1)
1−dα

=

1
2.

≥
By Lemma 7.1 and Claim 2 we conclude that for every vertex sequence x̄ with |Π(x̄)| ≤ t − s
we have
|{z̄ | (RI (G), z̄) ≃k (RI (G), Π(x̄))}| ≥ 2c|x̄|/2−s ≥ 2|x̄|/4−s .
(7.2)
(Here the extra 1/2 in the exponent comes from the fact that in Lemma 7.1 for each wi only one
xi ∈ F (wi ) can be chosen but here Π(x̄) can contain both vertices from F (wi ).)
Claim 3.

ref,sel
There is a sequence ȳ in Tinv
(RI (G)) with t − s − r < |Π(ȳ)| ≤ t − s.

ref,sel
Proof. Let x̄ be a leaf of Tinv
(RI (G)) and let m = |x̄| be the length of x̄. Observe that πi (x̄) :=
WLk ,sel
I
(x1 , . . . , xi ) ∈ V (Tinv
(R (G))) for every i ∈ [m]. Define ti as |Π(πi (x̄))|. Note that ti ≤ ti−1 + r
since |Π(xi )| ≤ r. It thus suffices to show that |Π(x̄)| > t − s − r. Assume otherwise. We show
that ref(RI (G), x̄) is not discrete and thus x̄ is not a leaf. Let x̄′ be a sequence of which x̄ is a prefix
that satisfies 4s < |Π(x̄′ )| ≤ t−s (possibly x̄′ = x̄). It suffices now to show that ref(RI (G), x̄′ ) is not
′
discrete. Indeed, by Equation (7.2) we have |{z̄ | (RI (G), z̄) ≃k (RI (G), Π(x̄′ ))}| ≥ 21/4|Π(x̄ )|−s >
2s−s = 1. Since RI is rigid, this implies that ref(RI (G), x̄′ ) is not discrete.
y

Applying the sequence ȳ from Claim 3 to Equation (7.2) we obtain that |{z̄ | (RI (G), z̄) ≃k
≥ 2c|ȳ|/2−s ≥ 2|ȳ|/4−s ≥ 2t/4−r/4−5/4s ≥ 2ℓ/12−ℓ/36−ℓ/36 ≥ 2ℓ/36 . By Claim 2 this
means that |{z̄ | (RI (G), z̄) ≃k (RI (G), ȳ)}| ≥ 2ℓ/36 . We conclude the proof by an application of
Lemma 3.3.
(RI (G), Π(ȳ))}|

Having already shown in the previous section the existence of graphs that satisfy the requirements of the theorem we just proved, we can now prove the main theorem.
Proof of Theorem 3.2. Theorem 3.2 now follows by combining Theorems 6.4 and 7.2.
While the graphs we have constructed are colored graphs, we should remark that it is not
difficult to turn them into uncolored graphs while preserving the exponential size of the search tree.
Indeed, we form the disjoint union of the graph RI (G) with a path of length t + 1 where t is the
number of colors in RI (G). We then order the colors and connect the i-th vertex of the path with
all vertices of color i. Finally we add a vertex adjacent to all but the last vertex of the path to
^
^
I (G). In the resulting uncolored graph R
I (G), the last vertex of the path is the
obtain a graph R
only vertex with degree 1. Moreover if we apply color-refinement then all newly added vertices are
^
I (G) is the same as it the
singletons and the partition induced by color classes on V (RI (G)) in R
^
I (G)
one in RI (G). This shows that the graph is still rigid. It also implies that each search tree of R
I
corresponds to a search tree of R (G) of the same size.

17

8

Component Recursion

Component recursion is a mechanism that can be used as addition to an individualization-refinement
algorithm improving their performance. With the right cell selection strategy, using component
recursion, individualization-refinement algorithms have exponential upper bounds [8].
Some form of component recursion is for example implemented in the newest version of bliss
and was demonstrated to yield significant improvements in practice [12]. In this section we argue
that for our examples it is not possible to beat the exponential lower bounds even with the use of
component recursion, which we explain first.
For a graph G = (V, E) we say that two disjoint vertex sets X, Y ⊆ V are uniformly joined
if E ∩ (X × Y ) = ∅ or E ∩ (X × Y ) = X × Y . By definition the sets are uniformly joined if X = ∅
or Y = ∅.
Definition 8.1. Let G = (V, E, c) be a colored graph and let S ⊆ V be a set of vertices. We say
that S is a color-component of G if for all colors i, j ∈ [n] the sets S ∩ c−1 (i) and c−1 (j) \ S are
uniformly joined.
We will not go into great detail on how color-components can be exploited by individualizationrefinement algorithms and rather refer to [12]. Intuitively, components can be used to treat parts
of the input graph independently. For us it will be sufficient to note the following. If a colorcomponent is a union of color classes (of the stable coloring under 1-dimensional Weisfeiler-Leman)
then a suitable cell selector can ensure that the component is explored entirely before the search
progresses into vertices outside of the color-component (see [12]). We will show now that for the
graphs that appear as nodes in the search tree of our graphs there are no color-components besides
those that are unions of color classes.
Definition 8.2. Let G = (V, E, c) be a colored graph and let X ⊆ V be a set of vertices. We say
that X respects color i ∈ [n] if either c−1 (i) ∩ X = ∅ or c−1 (i) ⊆ X.
Let G = (V, E, c) be a colored graph and let χ : V → [n] be a second coloring of the vertices.
We call χ an equitable coloring of G if χ  c and for all i, j ∈ [n] and all v, w ∈ χ−1 (i) it holds that
|N (v) ∩ χ−1 (j)| = |N (w) ∩ χ−1 (j)|.
Observe that a coloring χ is equitable if and only if it is not further refined by 1-dimensional
Weisfeiler-Leman, that is, χ is stable with respect to the 1-dimensional Weisfeiler-Leman algorithm.
Lemma 8.3. Let G = (V, W, E) be a bipartite graph and let χ be an equitable coloring of R(G).
Suppose S ⊆ V (R(G)) is a color-component of Rχ (G) = (V (R(G)), E(R(G)), χ). Then S is a union
of color classes of χ or the graph Rχ (G) has a non-trivial automorphism.
Proof. Suppose that S is not a union of color classes. Then there is some color i ∈ [n] such that
C1 := S ∩χ−1 (i) 6= ∅ and C2 := χ−1 (i)\S 6= ∅. Let c be the (original) coloring of R(G). Since χ  c,
there either is a vertex w ∈ W with C1 ∪ C2 ⊆ F (w) or there is some v ∈ V with C1 ∪ C2 ⊆ M (v).
Claim 1. S respects all colors i ∈ [n] for which |χ−1 (i)| ≥ 3.
Proof. Suppose otherwise that S does not respect i and choose v ∈ V such that χ−1 (i) ⊆ M (v).
Furthermore let A1 , A2 , A3 ⊆ N (v) be distinct subsets of even size such that χ(mAj (v)) = i for all
j ∈ {1, 2, 3}, mA1 (v) ∈ S and mA2 (v) ∈
/ S. Choose w1 ∈ A1 \ A2 and w2 ∈ A2 \ A1 . First observe
18

that F (w1 ) and F (w2 ) form color classes with respect to χ, because χ is equitable. Furthermore, S
does not respect the color classes F (w1 ) and F (w2 ).
Now assume without loss of generality that w1 ∈ A3 . We distinguish two cases. First suppose
that w2 ∈ A3 . If mA3 (v) ∈ S then S has to respect the color the color class F (w2 ). Otherwise
mA3 (v) ∈
/ S and S has to respect the color the color class F (w1 ). In both cases we obtain a
contradiction.
So w2 ∈
/ A3 . Let w3 ∈ A1 \ A3 . If mA3 (v) ∈ S then S has to respect the color the color class
F (w3 ). But mA2 (v) is only connected to one of the vertices {a(w3 ), b(w3 )} which again leads to a
contradiction. So mA3 (v) ∈
/ S. But then, looking at mA2 (v) and mA3 (v), S has to respect the color
class F (w2 ). Once again, this is a contradiction.
y
Now let M = {i ∈ [n] | S does not respect color i}. For each i ∈ M we have χ−1 (i) = {ai , bi }
where ai ∈ S and bi ∈ S. We define


/M
v if χ(v) ∈
γ : V (R(G)) → V (R(G)) : v → bi if v = ai for some i ∈ M .


ai if v = bi for some i ∈ M
Claim 2.

γ ∈ Aut(Rχ (G)).

Proof. Let {u, m} ∈ E(R(G)) where u ∈ F (w) for some w ∈ W and m ∈ M (v) for some v ∈ N (w).
First suppose γ(u) 6= u. Then χ(u) ∈ M and S does not respect the color class F (w). Without
loss of generality assume u = a(w) and thus, γ(u) = b(w). Since χ is equitable there is some
m′ ∈ NR(G) (b(w)) \ NR(G) (a(w)) with χ(m) = χ(m′ ). But then |S ∩ {m, m′ }| = 1 because S is a
color-component. Hence, S does not respect color χ(m) and χ−1 (χ(m)) = {m, m′ } by Claim 1. So
γ(m) = m′ and thus, {γ(u), γ(m)} ∈ E(R(G)).
Similarly, it also follows that {γ(u), γ(m)} ∈ E(R(G)) if γ(m) 6= m. So γ preserves the edge
relation of R(G) and thus, γ ∈ Aut(Rχ (G)).
y

Corollary 8.4. Let G = (V, W, E) be a bipartite graph. If RI (G) is rigid then every colorcomponent of RI (G) of an equitable coloring is a union of color classes.
As we mentioned before, color-components that are unions of color classes can be handled
with a suitable cell selector. We conclude that the lower bound of Theorem 3.2 also applies to
individualization-refinement algorithms that apply component recursion.

9

Discussion

We presented a construction resulting in graphs for which the search tree of individualizationrefinement algorithms has exponential size. As a consequence algorithms based on this paradigm
have exponential worst case complexity. In particular, this includes the to date fastest practical
isomorphism solvers such as nauty, traces, bliss, saucy and conauto.
While the analysis in this paper is theoretical, constructions related to the ones presented in
this paper produce graphs that constitute the practically most difficult instances to date [18].

19

Our construction gives, for each constant k, a family of graphs that lead to exponential size
search trees when the k-dimensional Weisfeiler-Leman algorithm is used as a refinement operator.
However, it is not clear whether we can obtain similar statements if the Weisfeiler-Leman dimension
may depend on the number of vertices of the input graph. The recent quasi-polynomial time
algorithm due to Babai [2] for example repeatedly benefits from performing the Θ(log n)-dimensional
Weisfeiler-Leman algorithm where n is the number of vertices of the input graphs. In particular,
it is an interesting question whether we still obtain exponential size search trees if we allow the
Weisfeiler-Leman dimension to be linear in the number of vertices. A related question asks for the
maximum Weisfeiler-Leman dimension of rigid graphs.
Another interesting question concerns the complexity of individualization-refinement algorithms
for other types of structures. Here, we are particularly interested in the group isomorphism problem
(for groups given by multiplication table). What is the running time of the individualizationrefinement paradigm for groups? In fact, it is not even known whether groups have bounded
Weisfeiler-Leman dimension. That is, whether there is a k for which the k-dimensional WeisfeilerLeman algorithm solves group isomorphism.
Finally, all known constructions leading to graphs with large Weisfeiler-Leman dimension are
in some way based on the CFI-construction, but it would be desirable to have constructions that
are conceptually different. Let us remark again that isomorphism for the graphs we constructed
can be decided im polynomial time using techniques from algorithmic group theory. It would be
interesting to find explicit constructions that are difficult for both group theoretic techniques and
methods based on the Weisfeiler-Leman algorithm.

References
[1] L. Babai. Monte carlo algorithms in graph isomorphism testing. Technical Report 79-10,
Université de Montréal, 1979.
[2] L. Babai. Graph isomorphism in quasipolynomial time [extended abstract]. In D. Wichs and
Y. Mansour, editors, Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of
Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 684–697. ACM, 2016.
[3] L. Babai and E. M. Luks. Canonical labeling of graphs. In D. S. Johnson, R. Fagin, M. L.
Fredman, D. Harel, R. M. Karp, N. A. Lynch, C. H. Papadimitriou, R. L. Rivest, W. L.
Ruzzo, and J. I. Seiferas, editors, Proceedings of the 15th Annual ACM Symposium on Theory
of Computing, 25-27 April, 1983, Boston, Massachusetts, USA, pages 171–183. ACM, 1983.
[4] J. Cai, M. Fürer, and N. Immerman. An optimal lower bound on the number of variables for
graph identifications. Combinatorica, 12(4):389–410, 1992.
[5] N. J. Calkin. Dependent sets of constant weight binary vectors. Combinatorics, Probability &
Computing, 6(3):263–271, 1997.
[6] P. Codenotti, H. Katebi, K. A. Sakallah, and I. L. Markov. Conflict analysis and branching
heuristics in the search for graph automorphisms. In 2013 IEEE 25th International Conference
on Tools with Artificial Intelligence, Herndon, VA, USA, November 4-6, 2013, pages 907–914.
IEEE Computer Society, 2013.

20

[7] M. L. Furst, J. E. Hopcroft, and E. M. Luks. Polynomial-time algorithms for permutation
groups. In 21st Annual Symposium on Foundations of Computer Science, Syracuse, New York,
USA, 13-15 October 1980, pages 36–41. IEEE Computer Society, 1980.
[8] M. Goldberg. A nonfactorial algorithm for testing isomorphism of two graphs. Discrete Applied
Mathematics, 6(3):229 – 236, 1983.
[9] Y. Gurevich and S. Shelah. On finite rigid structures. J. Symb. Log., 61(2):549–562, 1996.
[10] N. Immerman and E. Lander. Describing Graphs: A First-Order Approach to Graph Canonization, pages 59–81. Springer New York, New York, NY, 1990.
[11] T. Junttila and P. Kaski. Engineering an efficient canonical labeling tool for large and sparse
graphs. In D. Applegate, G. S. Brodal, D. Panario, and R. Sedgewick, editors, Proceedings of
the Ninth Workshop on Algorithm Engineering and Experiments and the Fourth Workshop on
Analytic Algorithms and Combinatorics, pages 135–149. SIAM, 2007.
[12] T. A. Junttila and P. Kaski. Conflict propagation and component recursion for canonical
labeling. In A. Marchetti-Spaccamela and M. Segal, editors, Theory and Practice of Algorithms
in (Computer) Systems - First International ICST Conference, TAPAS 2011, Rome, Italy,
April 18-20, 2011. Proceedings, volume 6595 of Lecture Notes in Computer Science, pages
151–162. Springer, 2011.
[13] J. L. López-Presa, A. F. Anta, and L. N. Chiroque. Conauto-2.0: Fast isomorphism testing
and automorphism group computation. CoRR, abs/1108.1060, 2011.
[14] B. D. McKay. Practical graph isomorphism. Congr. Numer., 30:45–87, 1981.
[15] B. D. McKay and A. Piperno. Practical graph isomorphism, II. J. Symb. Comput., 60:94–112,
2014.
[16] T. Miyazaki. The complexity of McKay’s canonical labeling algorithm. In Groups and Computation, volume 28 of DIMACS Series in Discrete Mathematics and Theoretical Computer
Science, pages 239–256. DIMACS/AMS, 1995.
[17] R. Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, 1995.
[18] D. Neuen and P. Schweitzer.
manuscript.

Benchmark graphs for practical graph isomorphism. 2017.

[19] S. P. Vadhan. Pseudorandomness. Foundations and Trends in Theoretical Computer Science,
7(1-3):1–336, 2012.

21

