An improved isomorphism test for bounded-tree-width graphs

arXiv:1803.06858v1 [] 19 Mar 2018

Martin Grohe† , Daniel Neuen† , Pascal Schweitzer‡ , and Daniel Wiebking†
†

RWTH Aachen University, {grohe,neuen,wiebking}@informatik.rwth-aachen.de
‡
University of Kaiserslautern, schweitzer@cs.uni-kl.de
March 20, 2018

Abstract
We give a new fpt algorithm testing isomorphism of n-vertex graphs of tree width k
in time 2k polylog(k) poly(n), improving the fpt algorithm due to Lokshtanov, Pilipczuk,
5
Pilipczuk, and Saurabh (FOCS 2014), which runs in time 2O(k log k) poly(n). Based
on an improved version of the isomorphism-invariant graph decomposition technique
introduced by Lokshtanov et al., we prove restrictions on the structure of the automorphism groups of graphs of tree width k. Our algorithm then makes heavy use of the
group theoretic techniques introduced by Luks (JCSS 1982) in his isomorphism test for
bounded degree graphs and Babai (STOC 2016) in his quasipolynomial isomorphism
test. In fact, we even use Babai’s algorithm as a black box in one place.
We also give a second algorithm which, at the price of a slightly worse running time
2
2O(k log k) poly(n), avoids the use of Babai’s algorithm and, more importantly, has the
additional beneﬁt that it can also used as a canonization algorithm.

1

Introduction

Already early on in the beginning of research on the graph isomorphism problem (which
asks for structural equivalence of two given input graphs) a close connection to the structure
and study of the automorphism group of a graph was observed. For example, Mathon
[Mat79] argued that the isomorphism problem is polynomially equivalent to the task of
computing a generating set for the automorphism group and also to computing the size of
the automorphism group.
With Luks’s polynomial time isomorphism test for graphs of bounded degree [Luk82],
the striking usefulness of group theoretic techniques for isomorphism problems became
apparent and they have been exploited ever since (e.g. [BL83, Mil83, Pon91, Neu16]). In
his algorithm, Luks shows and uses that the automorphism group of a graph of bounded
degree, after a vertex has been ﬁxed, has a very restricted structure. More precisely, the

1

group is in the class Γk of all groups whose non-Abelian composition factors are isomorphic
to a subgroup of the symmetric group Sym(k).
Most recently, Babai’s quasi-polynomial time algorithm for general graph isomorphism
[Bab16] adds several novel techniques to tame and manage the groups that may appear as
the automorphism group of the input graphs.
A second approach towards isomorphism testing is via decomposition techniques (e.g.
[Bod90, GM15, GS15]). These decompose the graph into smaller pieces while maintaining
control of the complexity of the interplay between the pieces. When taking this route it
is imperative to decompose the graph in an isomorphism-invariant fashion so as not to
compare two graphs that have been decomposed in structurally diﬀerent ways.
A prime example of this strategy is Bodlaender’s isomorphism test [Bod90] for graphs
of bounded treewidth. Bodlaender’s algorithm is a dynamic programming algorithm that
takes into account all k-tuples of vertices that separate the graph, leading to a running
time of O(nk+c ) to test isomorphism of graphs of tree width at most k.
Only recently, Lokshtanov, Pilipczuk, Pilipczuk, and Saurabh [LPPS17] designed a
ﬁxed-parameter tractable isomorphism test for graphs of bounded tree width which has a
5
running time of 2O(k log k) poly(n). This algorithm ﬁrst “improves” a given input graph G
to a graph Gk by adding an edge between every pair of vertices between which more than kinternally vertex disjoint paths exist. The improved graph Gk isomorphism-invariantly decomposes along clique separators into clique-separator free parts, which we will call basic
throughout the paper. The decomposition can in fact be extended to an isomorphisminvariant tree decomposition into basic parts, as was shown in [ES16] to design a logspace
isomorphism test for graphs of bounded tree width. For the basic parts, Lokshtanov et
al. [LPPS17] show that, after ﬁxing a vertex of suﬃciently low degree, is it possible to
compute an isomorphism-invariant tree decomposition whose bags have a size at most exponential in k and whose adhesion is at most O(k3 ). They use this invariant decomposition
to compute a canonical form essentially by a brute-force dynamic programming algorithm.
The problem of computing a canonical form is the task to compute, to a given input graph G, a graph G′ isomorphic to G such that the output G′ depends only on the
isomorphism class of G and not on G itself.
The isomorphism problem reduces to the task of computing a canonical form: for two
given input graphs we compute their canonical forms and check whether the canonical
forms are equal (rather than isomorphic).
As far as we know, computing a canonical form could be algorithmically more diﬃcult
than testing isomorphism. It is usually not very diﬃcult to turn combinatorial isomorphism
tests into canonization algorithms, sometimes the algorithms are canonization algorithms in
the ﬁrst place. However, canonization based on group theoretic isomorphism tests is more
challenging. For example, it is still open whether there is a graph canonization algorithm
running in quasipolynomial time.

2

Our Results
Our main result is a new fpt algorithm testing isomorphism of graphs of bounded tree
width.
Theorem 1. There is a graph isomorphism test running in time
2k polylog(k) poly(n),
where n is the size and k the minimum tree width of the input graphs.
In the ﬁrst part of the paper, we analyze the structure of the automorphism groups of a
graph G of tree width k. Following [LPPS17] and [ES16], we pursue a two-stage decomposition strategy for graphs of bounded tree width, where in the ﬁrst step we decompose the
improved graph along clique separators into basic parts. We observe that these basic parts
are essential for understanding the automorphism groups. We show (Theorem 9) that with
respect to a ﬁxed vertex v of degree at most k, we can construct for each basic graph H
an isomorphism-invariant tree decomposition of width at most 2O(k log k) and adhesion at
most O(k2 ) where, in addition, each bag is equipped with a graph of small degree which
is deﬁned in an isomorphism-invariant way and gives us insight about the structure of
the bag. In particular, using Luks results [Luk82], this also restricts the structure of the
automorphism group.
Our construction is based on a similar construction of an isomorphism-invariant tree
decomposition in [LPPS17]. Compared to that construction, we improve the adhesion (that
is, the maximum size of intersections between adjacent bags of the decomposition) from
O(k3 ) to O(k2 ). More importantly, we expand the decomposition by assigning a group and
a graph to each bag.
Using these groups, we can prove that Aut(H)v (the group of all automorphisms of
H that keep the vertex v ﬁxed) is a Γk+1 group. This signiﬁcantly restricts possible
automorphism groups. Moreover, using the graph structure assigned to each bag, we can
also compute the automorphism group of a graph of tree width k within the desired time
bounds. The ﬁrst, already nontrivial step towards computing the automorphism group, is
a reduction from arbitrary graphs of tree width k to basic graphs. The second step reduces
the problem of computing the automorphism group of a basic graph to the problem of
computing the automorphism group of a structure that we call an expanded d-ary tree.
In the reduction, the parameter d will be polynomially bounded in k. Then as the third
step, we can apply a recent result [GNS18] due to the ﬁrst three authors that allows us
to compute the automorphism groups of such expanded d-ary trees. This result is heavily
based on techniques introduced by Babai [Bab16] in his quasipolynomial isomorphism test.
In fact, it even uses Babai’s algorithm as a black box in one place.
We prove a second result that avoids the results of [GNS18, Bab16] and even allows us
to compute canonical forms, albeit at the price of an increased running time.

3

Theorem 2. There is a graph canonization algorithm running in time
2O(k

2

log k)

poly(n),

where n is the size and k the tree width of the input graph.
Even though it does not employ Babai’s new techniques, this algorithm still heavily
depends on the group theoretic machinery. As argued above, the design of group theoretic
canonization algorithms often requires extra work, and can be slightly technical, compared
to the design of an isomorphism algorithm. Here, we need to combine the group theoretic
canonization techniques going back to Babai and Luks [BL83] with graph decomposition
techniques, which poses additional technical challenges and requires new canonization subroutines.

Organization of the paper
In the next section we introduce the necessary preliminaries. The next two Sections 3–4
of the paper deal with the decomposition of bounded tree width graphs. They describe
the isomorphism-invariant decomposition into basic parts and the isomorphism-invariant
decomposition of the basic parts with respect to a ﬁxed vertex of low degree.
The two following Sections 5–6 are concerned with isomorphism. We deﬁne a particular subproblem, coset-hypergraph-isomorphism, identiﬁed to be of importance. Then, we
assemble the recursive isomorphism algorithm.
In the last Section 7 we devise several subroutines for canonization in general and
assemble the recursive canonization algorithm.

2

Preliminaries

Graphs We use standard graph notation. All graphs G = (V, E) considered are undirected ﬁnite simple graphs. We denote an edge {u, v} ∈ E by uv. Let U, W ⊆ V be subsets
of vertices. We write E(U, W ) for the edges with one vertex in U and the other vertex
from W , whereas E(U ) are the edges with both vertices in U . By N (U ), we denote the
neighborhood of U , i.e, all vertices outside U that are adjacent to U . For the induced
subgraph on U , we write G[U ], whereas G − U is the induced subgraph on V \ U . A rooted
graph is triple G = (V, E, r) where r ∈ V is the root of the graph. For two vertices v, w ∈ V
we denote by distG (v, w) the distance between v and w, i.e. the length of the shortest path
from v to w. The depth of a rooted graph is the maximum distance from a vertex to the
root, that is, depth(G) = maxv∈V distG (r, v). The forward-degree of a vertex v ∈ V is
fdeg(v) = |{w ∈ N (v) | dist(w, r) = dist(v, r) + 1}|. Note that |V | ≤ (d + 1)depth(G) where
d = maxv∈V fdeg(v) is the maximal forward-degree.

4

Separators A pair (A, B) where A∪B = V (G) is called a separation if E(A\B, B \A) =
∅. In this case we call A ∩ B a separator. A separation (A, B) is a (L, R)-separation if
L ⊆ A and R ⊆ B and in this case A ∩ B is called a (L, R)-separator. A separation (A, B)
is a called a clique separation if A ∩ B is a clique and A \ B 6= ∅ and B \ A 6= ∅. In this
case we call A ∩ B a clique separator.
Tree Decompositions
Definition 3. A tree decomposition of a graph G is a pair (T, β), where T is a rooted tree
and β : V (T ) → Pow(V (G)) is a mapping into the power set of V (G) such that:
1. for each vertex v ∈ V (G), the set {t ∈ V (G) | v ∈ β(t)} induces a nonempty and
connected subtree of T, and
2. for each edge e ∈ E(G), there exists t ∈ V (T ) such that e ⊆ β(t).
Sets β(t) for t ∈ V (T ) are called the bags of the decomposition, while sets β(s) ∩ β(t)
for st ∈ E(T ) are called the adhesions sets. The width of a tree decomposition T is equal
to its maximum bag size decremented by one, i.e. maxt∈V (T ) |β(t)| − 1. The adhesion width
of T is equal to its maximum adhesion size, i.e., maxst∈E(T ) |β(s) ∩ β(t)|. The tree width
of a graph, denoted by tw(G), is equal to the minimum width of its tree decompositions.
A graph G is k-degenerate if every subgraph of G has a vertex with degree at most k.
It is well known that every graph of tree width k is k-degenerate.
Groups For a function ϕ : V → V ′ and v ∈ V we write v ϕ for the image of v under
ϕ, that is, v ϕ = ϕ(v). We write composition of functions from left to right, e.g, v (σρ) =
(v σ )ρ = ρ(σ(v)). By [t] we denote the set of natural number from 1 to t. By Sym(V ) we
denote the symmetric group on a set V and we also write Sym(t) for Sym([t]). We use
upper Greek letters ∆, Φ, Γ, Θ and Ψ for permutation groups.
Labeling cosets A labeling coset of a set V is a set of bijective mappings τ ∆ where
τ is a bijection from V to [|V |] and and ∆ is a subgroup of Sym(|V |). By Label(V ), we
denoted the labeling coset τ Sym(|V |). We say that τ ∆ is a labeling subcoset of a labeling
coset ρΘ, written τ ∆ ≤ ρΘ, if τ ∆ is a subset of ρΘ and τ ∆ forms a labeling coset again.
Sometimes we will choose a single symbol to denote a labeling coset τ ∆. For this will
usually use the upper greek letter Λ. Recall that Γk denotes the class of all ﬁnite groups
e k be
whose non-Abelian composition factors are isomorphic to subgroups of Sym(k). Let Γ
the class of all labeling cosets Λ = τ ∆ such that ∆ ∈ Γk .
Orderings on sets of natural numbers We extend the natural ordering of the natural
numbers to ﬁnite sets of natural numbers. For two such sets M1 , M2 we deﬁne M1 ≺ M2
if |M1 | < |M2 | or if |M1 | = |M2 | and the smallest element of M1 \ M2 is smaller than the
smallest element of M2 \ M1 .
5

Isomorphisms In this paper we will always deﬁne what the isomorphism between our
considered objects are. But this can also be done in a more general context. Let ϕ : V → V ′ .
For a vector (v1 , . . . , vk ) we deﬁne (v1 , . . . , vk )ϕ as (v1ϕ , . . . , vkϕ ) inductively. Analogously,
for a set we deﬁne {v1 , . . . , vn }ϕ as {v1ϕ , . . . , vnϕ }. For a labeling coset Λ ≤ Label(V ) we
write Λϕ for ϕ−1 Λ. In the paper we will introduce isomorphisms Iso(X, X ′ ) for various
objects X and X ′ . Unless otherwise stated these are all ϕ : V → V ′ such that X ϕ = X ′
where we apply ϕ as previously deﬁned. For example, the isomorphism between two graphs
G and G′ are all ϕ : V → V ′ such that Gϕ = G′ which means that G has an edge uv, if
and only if G′ has the edge uϕ v ϕ .

3

Clique separators and improved graphs

To perform isomorphism tests of graphs of bounded tree width, a crucial step in [LPPS17]
is to deal with clique separators. For this step the concept of a k-improved graph is the
key.
Definition 4 ([LPPS17]). The k-improvement of a graph G is the graph Gk obtained from
G by connecting every pair of non-adjacent vertices v, w for which there are more than k
pairwise internally vertex disjoint paths connecting v and w. We say that a graph G is
k-improved when Gk = G.
A graph is k-basic if it is k-improved and does not have any separating cliques. In
particular, a k-basic graph is connected.
We summarize several structural properties of Gk .
Lemma 5 ([LPPS17]). Let G be a graph and k ∈ N.
1. The k-improvement Gk is k-improved, i.e., (Gk )k = Gk .
2. Every tree decomposition (T, β) of G of width at most k is also a tree decomposition
of Gk .
3. There exists an algorithm that, given G and k, runs in O(k2 n3 ) time and either
correctly concludes that tw(G) > k, or computes Gk .
Since the construction of Gk from G is isomorphism-invariant, the concept of the improved graph can be exploited for isomorphism testing and canonization. A k-basic graph
has severe limitations concerning its structure as we explore in the following sections. In
the canonization algorithm from [LPPS17] a result of Leimer [Lei93] is exploited that
says that every graph has a tree decomposition into clique-separator free parts, and the
family of bags is isomorphism-invariant. While it is usually suﬃcient to work with an
isomorphism-invariant set of bags (see [OS14]) we actually require an isomorphism invariant decomposition, which can indeed be obtained.
6

Theorem 6 ([Lei93],[ES16]). There is an algorithm that, given a connected graph G,
computes a tree decomposition (T, β) of G, called clique separator decomposition, with the
following properties.
1. For every t ∈ V (T ) the graph G[β(t)] is clique-separator free (and in particular
connected).
2. Each adhesion set of (T, β) is a clique.
3. |V (T )| ∈ O(|V (G)|).
4. For each bag β(t) the adhesion sets of the children are all equal to β(t) or the adhesion
sets of the children are all distinct.
The algorithm runs in polynomial time and the output of the algorithm is isomorphisminvariant (w.r.t. G).

4

Decomposing basic graphs

In this section, we shall construct bounded-width tree decompositions of k-basic graphs of
tree width at most k. Crucially, these decompositions will be isomorphism invariant after
ﬁxing one vertex of the graph. Our construction reﬁnes a similar construction of [LPPS17].
Let us deﬁne three parameters cS , cM , and cL (small, medium and large) that depend
on k as follows:


cM 2
.
cS := 6(k + 1),
cM := cS + cS (k + 1),
cL := cM + 2(k + 1)
k+2
Note that cS ∈ O(k), cM ∈ O(k2 ) and cL ∈ 2O(k log k) . The interpretation of these
parameters is that cM will bound the size of the adhesion sets and cL will bound the
bag size. The parameter cS is used by the algorithm which in certain situations behaves
diﬀerently depending on sets being larger than cS or not.
The bound cM ∈ O(k2 ) improves the corresponding bound cM ∈ O(k3 ) in [LPPS17].
However, the more signiﬁcant extension of the construction in [LPPS17] is that in addition to the tree decomposition we also construct both an isomorphism-invariant graph of
bounded forward-degree and depth and an isomorphism-invariant Γk+1 -group associated
with each bag.
P The weight of a set S ⊆ V (G) with respect to a (weight) function w : V (G) → N is
v∈S w(v). The weight of a separation (A, B) is the weight of its separator A ∩ B. For
sets L, R ⊆ V (G), among all (L, R)-separations (A, B) of minimal weight there exists a
unique separation with an inclusion minimal A. For this separation we call A ∩ B the
leftmost minimal separator and denote it by SL,R (w). Moreover, we deﬁne SL,R = SL,R (1)
where 1 denotes the function that maps every vertex to 1.
7

For U ⊆ V (G) we deﬁne a weight function wU,k such that wU,k (u) = k for all u ∈ U
and wU,k (v) = 1 for all v ∈ V \ U . Given a weight function w, using Menger’s theorem
and the Ford-Fulkerson algorithm it is possible to compute SL,R (w). The following lemma
generalizes Lemma 3.2 of [LPPS17]. Through this generalization we obtain the adhesion
bound O(k2 ) for our decomposition.
Lemma 7. Let G be a graph, let S ⊆ V (G) be a subset of vertices, and let {Ti ⊆ V (G)}i∈[t]
and {wi : V (G) → N}i∈[t] be families where each Ti is a minimum weight (Li , Ri )-separator
with respect to wi for some Li , Ri ⊆ S. Let w : V (G) → N be another weight function such
that for all i ∈ [t]:
1. w(v) = wi (v) for all v ∈ V (G) \ S, and
2. w(v) ≥ wi (v) for all v ∈ V (G).
S
Let D := S ∪ i∈[t] Ti . Suppose that Z is the vertex set of any connected component of
G − D. Then w(N (Z)) ≤ w(S).
Proof. We proceed by induction on t. For t = 0Swe have N (Z) ⊆ D = S, so the claim
is trivial. Assume t ≥ 1 and deﬁne D ′ := S ∪ i∈[t−1] Ti . Let Z be the vertex set of
a connected component of G − D, and let Z ′ ⊇ Z be the vertex set of the connected
component of G − D ′ containing Z. Let Lt , Rt ⊆ S be sets such that Tt is a minimum
weight (Lt , Rt )-separator with respect to wt . Let (A, B) be an (Lt , Rt )-separation with
separator A ∩ B = Tt . Without loss of generality we may assume that Z ⊆ A \ B. The
three sets A\Tt , Tt , and B\Tt partition V (G). Similarly the three sets V \(Z∪N (Z ′ )), N (Z ′ )
and Z ′ partition V (G). We deﬁne Qi,j to be the intersection of the i-th set of the ﬁrst
triple with the j-th set of the second triple. This way the sets Qi,j with i, j ∈ {1, 2, 3}
partition V (G) into 9 parts as shown in Figure 1.
We have w(N (Z ′ )) ≤ w(S) by the induction hypothesis. Since N (Z ′ ) = Q1,2 ∪Q2,2 ∪Q3,2
and N (Z) ⊆ Q1,2 ∪ Q2,2 ∪ Q2,3 , it suﬃces to show w(Q2,3 ) ≤ w(Q3,2 ). Observe that
Q2,1 ∪ Q2,2 ∪ Q3,2 is also an (Lt , Rt )-separator, because Lt ⊆ A and Rt ⊆ B by the choice
of (A, B), and Rt ⊆ S ⊆ V (G) \ Z ′ .
By the minimality of Tt , we have wt (Tt ) ≤ wt (Q2,1 ∪ Q2,2 ∪ Q3,2 ), and as Tt = Q2,1 ∪
Q2,2 ∪ Q2,3 , this implies wt (Q2,3 ) ≤ wt (Q3,2 ). By Assumptions (1) and (2) of the lemma,
it follows that
2
1
w(Q2,3 ) = wt (Q2,3 ) ≤ wt (Q3,2 ) ≤ w(Q3,2 ).
The lemma can be used to extend a set of vertices S that is not a clique separator
to a set D in an isomorphism-invariant fashion while controlling the size of the adhesions
sets of the components of G − D. It will be important for us that we can also extend a
labeling coset of S to a labeling coset of D and furthermore construct a graph of bounded
forward-degree and depth associated with D and S.

8

Q3,1

Q2,1

Q1,1

V \ (Z ′ ∪ N (Z ′ ))

S
Q3,2

Q2,2

Q1,2

N (Z ′ )
N (Z)

Q3,3

Q2,3

Q1,3

Z′

Z

A \ Tt

B \ Tt

Tt

Figure 1: Sets appearing in the proof of Lemma 7.
Lemma 8. Let k ∈ N and let G be a graph that is k-improved. Let S ⊆ V (G) and let
Λ ≤ Label(S) be a labeling coset such that
1. ∅ ( S ( V (G),

4. G − S is connected,

2. |S| ≤ cM ,

5. S = NG (V (G) \ S), and

3. S is not a clique,

e k+1 .
6. Λ ∈ Γ

There is an algorithm that either correctly concludes that tw(G) > k, or finds a proper
b ≤ Label(D) and a connected rooted graph H with
superset D of S and a labeling coset Λ
the following properties:
(A) D ) S,
(B) |D| ≤ cL ,

(C) if Z is the vertex set of any connected
component of G−D, then |N (Z)| ≤ cM ,
b∈Γ
e k+1 ,
(D) Λ

(E) D ⊆ V (H), depth(H) ≤ k + 3 and fdeg(v) ∈ kO(1) for all v ∈ V (H).
b H) is isomorphismThe algorithm runs in time 2O(k log k) |V (G)|O(1) and the output (D, Λ,
invariant (w.r.t. the input data G, S, Λ and k).
9

Here, the output of an algorithm A is isomorphism-invariant if all isomorphisms between two input data (G, S, Λ, k) and (G′ , S ′ , Λ′ , k′ ) extends to an isomorphism between the
b H) and (D ′ , Λ
b ′ , H ′ ) (An isomorphism between (G, S, Λ, k) and (G′ , S ′ , Λ′ , k′ )
output (D, Λ,
is a mapping ϕ : V (G) → V (G′ ) such that (G, S, Λ, k)ϕ = (G′ , S ′ , Λ′ , k′ ) where we apply ϕ
as deﬁned in the preliminaries).
Proof. We consider two cases depending on the size of S.
Case |S| ≤ cS : Let I := {({x}, {y}) | x, y ∈ S, x 6= y, xy ∈
/ E(G)} and let
[
D=S∪
SL,R (wL∪R,k+1 ).
(L,R)∈I

We set w := wS,k+1 and then we have the following for every vertex set Z of a
connected component of G − D by Lemma 7:
7
|N (Z)| ≤ w(N (Z)) ≤ w(S) ≤ cS (k + 1) ≤ cM .
For every xy ∈
/ E(G) there is a ({x}, {y})-separator of size at most k disjoint
from {x, y}, because G is k-improved. Thus |D| ≤ |S| + k|S|2 ≤ cS + kc2S ≤ cL .
Moreover, since G − S is connected and S = NG (V (G) \ S), for all distinct x, y ∈ S
every minimum weight ({x}, {y})-separator contains a vertex that is not in S. It
follows that D 6= S.
Case cS < |S| ≤ cM : Let I := {(L, R) | |L| = |R| ≤ k + 2, |SL,R | ≤ k + 1} and let
[
D=S∪
SL,R .
(L,R)∈I

The properties of D follow from similar arguments as in the ﬁrst case. The fact that I is
nonempty follows from the existence of a balanced separation (for details see [LPPS17]).
b in both cases. To each x ∈ D \ S we associate the set
Next, we show how to ﬁnd Λ
Ax := {(L, R) ∈ I | x ∈ SL,R }. Two vertices x and y occur in exactly the same separators
if Ax = Ay . In this case we call them equivalent and write x ≡ y. Let A1 , . . . , At ⊆ D \ S
be the equivalence classes of “≡”. Since each x is contained in some separator of size at
most k + 1 we conclude that the size of each Ai is at most k + 1.
b : D → {1, . . . , |D|} such that
For each labeling λ ∈ Label(S) we choose an extension λ
b
b
λ
λ
λ
λ
b S = λ and for x, y ∈ D\S we have x < y if A ≺ A . (Recall that ≺ is the linear order of
λ|
x
y
subsets of N as deﬁned in the preliminaries). Inside each equivalence class Ai , the ordering is
b | λ ∈ Λ} ≤ Label(D).
b := ({idS }×Sym(A1 )×. . .×Sym(At ))·{λ
chosen arbitrarily. Deﬁne Λ
b Since
b does not depend on the choices of the extensions λ.
By construction the coset Λ
b
e
|Ai | ≤ k + 1 for all 1 ≤ i ≤ t we conclude that Λ ∈ Γk+1 , as desired.
10

b For this we simply remark that is
It remains to explain how to eﬃciently compute Λ.
suﬃces to use a set of extensions M ⊆ Λ such that Λ is the smallest coset containing all
b
elements of M (i.e., we can use a coset analogue of a generating set). We conclude that Λ
can be computed in polynomial time in the size of I.
Last but not least, we show how to construct the graph H. The Case |S| ≤ cS is easy
to handle. In this case we deﬁne H as the complete graph on the set D ∪ {r} where r is
some new vertex, which becomes the root of H. The forward-degree of r is bounded by
|D| which in turn is bounded by kO(1) . We consider the Case cS < |S| ≤ cM . We deﬁne
V (H) := {(L, R) | L, R ⊆ S, |L| = |R| ≤ k + 2} ∪ D. Clearly, we have I ⊆ V (H). For the
root we choose (∅, ∅) ∈ V (H). We deﬁne the edges E(H) := {(L, R)(L′ , R′ ) | L ⊆ L′ , R ⊆
R′ , |L| + 1 = |R| + 1 = |L′ | = |R′ |} ∪ {x(L, R) | x ∈ D, x ∈ SL,R }. Since for each pair (L, R)
there are at most |S|2 diﬀerent extensions (L′ , R′ ) with |L| + 1 = |R| + 1 = |L′ | = |R′ | and
since each separator SL,R contains at most k + 1 vertices, we conclude that the forwarddegree of each vertex in H is bounded by |S|2 + k + 1 ∈ k O(1) . Moreover, the depth of H
is bounded by k + 3.
A labeled tree decomposition (T, β, α, η) is a 4-tuple where (T, β) is a tree decomposition
and α is a function that maps each t ∈ V (T ) to a labeling coset α(t) ≤ Label(β(t)) and η
is a function that maps each t ∈ V (T ) to a graph η(t).
The lemma can be used as a recursive tool to compute our desired isomorphisminvariant labeled tree decomposition.
Theorem 9. Let k ∈ N and let G be a k-basic graph and let v be a vertex of degree at
most k. There is an algorithm that either correctly concludes that tw(G) > k, or computes
a labeled tree decomposition (T, β, α, η) with the following properties.
(I) the width of (T, β) is bounded by cL ,
(II) the adhesion width of (T, β) is bounded by cM ,
(III) the degree of (T, β) is bounded by kc2L and the number of children of t with common
adhesion set is bounded by k for each t ∈ V (T ),
(IV) |V (T )| is bounded by O(|V (G)|),
(V) for each bag β(t) the adhesion sets of the children are all equal to β(t) or the adhesion
sets of the children are all distinct. In the former case the bag size is bounded by cM ,
(VI) for each t ∈ V (T ) the graph η(t) = Ht is a connected rooted graph such that β(t) ∪
β(t)2 ⊆ V (Ht ) and for each adhesion set S there is a corresponding vertex S ∈ V (Ht ),
depth(Ht ) ∈ O(k) and fdeg(v) ∈ kO(1) for all v ∈ V (Ht ), and
ek+1 .
(VII) α(t) ∈ Γ
11

2

The algorithm runs in time 2O(k log k) |V (G)|O(1) and the output (T, β, α, η) of the algorithm
is isomorphism invariant (w.r.t. G, v and k). Furthermore, if we drop Property (VII) as a
requirement, the triple (T, β, η) can be computed in time 2O(k log k) |V (G)|O(1) .
Here, the output of an algorithm A is isomorphism-invariant, if all isomorphisms between two input data extend to an isomorphism between the output. More precisely,
an isomorphism ϕ ∈ Iso((G, v, k), (G′ , v ′ , k′ )) extends to an isomorphism between between (T, β, α, η) and (T ′ , β ′ , α′ , η ′ ) if there is a bijection between the tree decompositions
ϕT : V (T ) → V (T ′ ) and for each node t ∈ V (T ) a bijection between the vertices of graphs
ϕt : V (η(t)) → V (η ′ (ϕT (t))) which extend ϕ, i.e. ϕt (x) = xϕ for all x ∈ β(t) ∪ β(t)2 ∪ 2β(t)
where we naturally apply ϕ as deﬁned in the preliminaries. Furthermore, these extensions
deﬁne an isomorphism between the output data, i.e. for all nodes t ∈ V (T ) we have that
β(t)ϕ = β ′ (ϕT (t)), α(t)ϕ = α′ (ϕT (t)) and η(t)ϕt = η ′ (ϕT (t)).
Proof. We describe a recursive algorithm A that has (G, S ⊆ V (G), Λ ≤ Label(S)) as the
input such that the data satisfy the assumptions of Lemma 8. That is:
1. ∅ ( S ( V (G),

4. G − S is connected,

2. |S| ≤ cM ,

5. S = NG (V (G) \ S) and,

3. S is not a clique or |N (S)| ≤ k,

e k+1 .
6. Λ ∈ Γ

The output is a labeled tree decomposition (T, β, α, η) with root bag S. Since G has no
separating cliques and therefore v is not a cut vertex, the triple (G, {v}, {v 7→ 1}) fulﬁlls
the input conditions which will complete the proof. The algorithm A works as follows.
b for the root node t ∈ V (T ).
Step 1: We describe how to construct β(t) = D and α(t) = Λ
If S is a clique we deﬁne D := S ∪ N (S). Notice that N (S) ≤ k due to Property
b :=
3. Let τ : N (S) → {|S| + 1, . . . , |D|} be an arbitrary bijection. We deﬁne Λ
Λ × τ Sym({|S| + 1, . . . , |D|}) ≤ Label(D). Otherwise (i.e., S is not a clique) we
b as in Lemma 8.
compute and deﬁne D and Λ
Let Z1 , . . . , Zr be the connected components of the graph G − D. Let Si := NG (Zi ) and
Gi := G[Zi ∪ Si ].
Step 2: We describe how to construct the graph η(t) = Ht . First, we compute the graph
H as in Lemma 8. To achieve that pairs of vertices from β(t) are contained in this
graph we deﬁne a Cartesian product H 2 , i.e. V (H 2 ) = V (H)2 and
E(H 2 ) =

{(u1 , u2 )(v1 , v2 ) | u1 v1 ∈ E(H) and u2 = v2 }
∪{(u1 , u2 )(v1 , v2 ) | u2 v2 ∈ E(H) and u1 = v1 }.

Now, we deﬁne Ht as follows. The vertex set is V (Ht ) := V (H)∪V (H 2 )∪{Si | i ∈ [r]}.
The edge set is E(Ht ) := E(H 2 )∪{(v, v)v | v ∈ H}∪{(u, v)Si | u, v ∈ Si , uv ∈
/ E(D)}
and the root of Ht is (r, r) where r is the root of H.
12

Step 3: We call the algorithm recursively as follows. Let
b S | Siλ = min{Siλ | λ ∈ Λ}}.
b
Λi := {λ ∈ Λ|
i
≺

(This set is essentially only an isomorphism-invariant restriction of Λ to Si . The minimum is taken with respect to ≺, the ordering of subsets of N as deﬁned in the preliminaries.) The image Siλ might be a set of natural numbers diﬀerent from {1, . . . , |Si |}.
To rectify this we let πi be the bijection from Siλ to {1, . . . , |Si |} that preserves
the normal ordering “<” of natural numbers and set Λ′i = Λi πi . We compute
A(Gi , Si , Λ′i ) = (Ti , βi , αi , ηi ) recursively. By possibly renaming the vertices of the
trees Ti , we can assume w.l.o.g. V (Ti ) ∩ V (Tj ) = ∅.
Step 4: We deﬁne a labeled tree decomposition (T, β, α, η) as follows. Deﬁne a new root
vertex t and attach the root vertices t1 , . . . , tr computed by the recursive calls as chilb and η(t) := Ht . Combine all decompositions
dren. We deﬁne β(t) := D and α(t) := Λ
(Ti , βi , αi , ηi ) together with the new root t and return the resulting decomposition
(T, β, α, η).
(Correctness.) First of all, we show that (Gi , Si , Λi ) fulﬁlls the Conditions 1-6 and the
b satisfy
recursive call in Step 3 is justiﬁed. Condition 1 is clear. For 2 notice that D and Λ
(A)-(D) from Lemma 8 regardless which option is applied in Step 1. Condition 2 then
follows from (C). For 3 notice that G does not have any separating cliques, but Si is a
separator. The Conditions 4 and 5 follow from the deﬁnition of Gi and Si , whereas 6
follows from (D).
Next, we show (I)-(V). The bound for the width in (I) immediately follows from (B),
while the bound on the adhesion width in (II) follows from (C). For (III) observe that
G is k-improved and therefore each non-edge in D is contained in at most k diﬀerent Si ,
i.e., |{i | u, v ∈ Si }| ≤ k for each u, v ∈ D, uv ∈
/ E(D). Therefore, r ≤ k|E(D)| ≤ kc2L .
Moreover, since each Sj contains a non-edge uv we conclude |{i | Si = Sj }| ≤ |{i | u, v ∈
Si }| ≤ k. For (IV) we associate each bag β(t) = D with the set D \ S in an injective
way. The number of sets D \ S occurring in each recursive call is bounded by |V (G)| since
these sets are not empty and pairwise distinct. We conclude |V (T )| ≤ |V (G)|. Property
(VII) follows from (D). For any bag not satisfying Property (V) we introduce a new bag
containing all equal adhesion sets. For (VI) we observe that the forward-degree of the
vertices (u, v) ∈ V (H 2 ) is the sum of the forward-degrees of u and v in H. The depth of
H 2 is twice the depth of H. Therefore, we have fdeg(x) ∈ k O(1) for each x ∈ V (Ht ) and
depth(Ht ) ≤ 2k + 7. The construction is obviously isomorphism invariant.
(Running time.) We have already seen that the number of recursive calls is bounded
b as in Lemma 8 can be done in time
by |V (G)|. The computation of the sets D and Λ
O(k
log
k)
O(1)
b With standard group
2
|V (G)|
. We need to explain how to compute Λi from Λ.
theoretic techniques, including the Schreier-Sims algorithm, one can ﬁnd a minimal image
13

b mapping to this minimal
of Si . Using set transporters one can ﬁnd all labelings in Λ
2 log k)
O(k)
O(k
image. This algorithm runs in time |D|
⊆ 2
. Since we are only interested
b
in an isomorphism invariant restriction of Λ to Si , we could also use techniques from
Section 7 as follows. We deﬁne a hypergraph X on the vertex set D consisting of one
b S be the restriction of a canonical labeling of
single hyperedge Si . Let Λi := CL(X; Λ)|
i
that hypergraph. This algorithm also runs in time |D|O(k) . This leads to a total run time
2
b is only needed if
of 2O(k log k) |V (G)|O(1) . We remark that the computation of Λi from Λ
we require Property (VII). For the computation of a labeled tree decomposition (T, β, η)
the bottleneck arises in Lemma 8 which gives a run time of 2O(k log k) |V (G)|O(1) .
Remark 10. We later use the isomorphism-invariance of the labeled tree decomposition
(T, β, α, η) from the previous theorem in more detail. Let t ∈ V (T ) be a non-root node
and let S ⊆ V (G) be the adhesion set to the parent node of t and let It = (Tt , βt , αt , ηt ) be
the decomposition of the subtree rooted at t and Gt the graph corresponding to It . Then
ηt is isomorphism-invariant w.r.t. Tt , βt , Gt and S.

5

Coset-Hypergraph-Isomorphism

After having computed isomorphism-invariant tree decompositions in the previous sections
we now want to compute the set of isomorphisms from one graph to another in a bottom
up fashion. Let G1 , G2 be the two input graphs and suppose we are given isomorphisminvariant tree decompositions (T1 , β1 ) and (T2 , β2 ). For a node t ∈ V (Ti ) we let (Gi )t be
graph induced by the union of all bags contained in the subtree rooted at t. The basic
idea is to compute for all pairs t ∈ V (T1 ), t′ ∈ V (T2 ) the set of isomorphisms from (G1 )t to
(G1 )t′ (in addition the isomorphisms shall also respect the underlying tree decomposition)
in a bottom up fashion.
The purpose of this section is to give an algorithm that solves this problem at a given
bag (assuming we have already solved the problem for all paris of children of t and t′ ). Let
us ﬁrst give some intuition for this task. Suppose we are looking for all bijections from
β1 (t) to β2 (t′ ) that can be extended to an isomorphism from (G1 )t to (G2 )t′ . Let t1 , . . . , tℓ
be the children of t and t′1 , . . . , t′ℓ the children of t′ . Then we essentially have to solve the
following two problems. First, we have to respect the edges appearing in the bags β1 (t)
and β2 (t′ ). But also, every adhesion set β(t) ∩ β(ti ) has to be mapped to another adhesion
set β(t′ ) ∩ β(t′j ) in such a way that the corresponding bijection (between the adhesion
sets) extends to an isomorphism from (G1 )ti to (G2 )t′j . In order to solve this problem we
ﬁrst consider the case in which the adhesion sets are all distinct and deﬁne the following
abstraction.
An instance of coset-hypergraph-isomorphism is a tuple I = (V1 , V2 , S1 , S2 , χ1 , χ2 , F, f)
such that
1. Si ⊆ Pow(Vi ),
14

2. χi : Si → N is a coloring,
3. F = {ΘS ≤ Sym(S) | S ∈ S1 }, and
4. f = {τS1 ,S2 : S1 → S2 | S1 ∈ S1 , S2 ∈ S2 such that χ1 (S1 ) = χ2 (S2 )} such that
(a) every τS1 ,S2 ∈ f is bijective, and
−1
′
(b) for every color i ∈ N and every S1 , S1′ ∈ χ−1
1 (i) and S2 , S2 ∈ χ2 (i) and θ ∈
ΘS1 , θ ′ ∈ ΘS1′ it holds that

θτS1,S2 (τS1′ ,S2 )−1 θ ′ τS1′ ,S2′ ∈ ΘS1 τS1′ ,S2 .

(N)

The instance is solvable if there is a bijective mapping ϕ : V1 → V2 such that
1. S ∈ S1 if and only if S ϕ ∈ S2 for all S ∈ Pow(V1 ),
2. χ1 (S) = χ2 (S ϕ ) for all S ∈ S1 , and
3. for every S ∈ S1 it holds that ϕ|S ∈ ΘS τS,S ϕ .
In this case we call ϕ an isomorphism of the instance I. Moreover, let Iso(I) be the set of
all isomorphisms of I. Observe that property (N) describes a consisteny condition: if we
can use σ1 to map S1 to S2 , σ2 to map S1′ to S2 , and σ3 to map S1′ to S2′ , then mapping
σ1 σ2−1 σ2 can be used to map S1 to S2′ . As a result the set of all isomorphisms of the
instance I forms a coset, that is Iso(I) = Θϕ for some Θ ≤ Sym(V1 ) and ϕ ∈ Iso(I).
In the application in the main recursive algorithm, the sets Vi = β(ti ), the hyperedges
Si are the adhesion sets of ti (and we will also encode the edges appearing in the bag in
this way), and the cosets ΘS1 τS1 ,S2 tell us which mappings between the adhesion sets S1
and S2 extend to an isomorphism between the corresponding subgraphs. The colorings
χ1 are used to indicate which subgraphs can not be mapped to each other (and also to
distinguish between the adhesion sets and egdes of the bags which will both appear in the
set of hyperedges).
The next Lemma gives us one of the central subroutines for our recursive algorithm.
Lemma 11. Let I = (V1 , V2 , S1 , S2 , χ1 , χ2 , F, f) be an instance of coset-hypergraph-isomorphism. Moreover, suppose there are isomorphism-invariant rooted graphs H1 = (W1 , E1 , r1 )
and H2 = (W2 , E2 , r2 ) such that
1. Vi ∪ Si ⊆ Wi ,
2. fdeg(w) ≤ d for all w ∈ Wi ,
3. depth(Hi ) ≤ h, and
4. |S| ≤ d for all S ∈ Si
15

for all i ∈ {1, 2}. Then a representation for the set Iso(I) can be computed in time
c
2O(h·log d) for some constant c.
Here, isomorphism-invariant means that for every isomorphism ϕ ∈ Iso(I) there is an
isomorphism ϕH from H1 to H2 such that v ϕ = v ϕH for all v ∈ V1 and {v ϕ | v ∈ S} = S ϕH
for all S ∈ S1 .
The proof of this lemma is based on the following theorem. A rooted tree T = (V, E, r)
is d-ary if every node has at most d children. An expanded rooted tree is a tuple (T, C)
where T = (V, E, r) is a rooted tree and C : L(T )2 → rg(C) is a coloring of pairs of leaves
of T (L(T ) denotes the set of leaves of T ). Isomorphisms between expanded trees (T, C)
and (T, C ′ ) are required to respect the colorings C and C ′ .
Theorem 12 ([GNS18]). Let (T, C) and (T ′ , C ′ ) be two expanded d-ary trees and let Γ ≤
Aut(T ) and γ ∈ Iso(T, T ′ ). Then one can compute a representation of the set {ϕ ∈ Γγ |
c
(T, C)ϕ = (T ′ , C ′ )} in time nO(log d) for some constant c.
Proof of Lemma 11. For i ∈ {1, 2} let Hi′ be the graph obtained from Hi by adding, for
each Si ∈ Si , vertices (Si , v) for every v ∈ Si connected to the vertex Si . Note that
depth(Hi′ ) ≤ h + 1 and fdeg(w) ≤ 2d for all w ∈ V (Hi′ ). Let ri be the root of Hi′ .
A branch of the graph Hi′ is a sequence of vertices (v0 , . . . , vk ) such that vj−1 vj ∈ E(Hi′ )
for every j ∈ [k] and dist(ri , vj ) = j for all j ∈ {0, . . . , k} (in particular v0 = ri ). We
construct a rooted 2d-ary tree Ti as follows. Let V (Ti ) be the set of all branches of
Hi′ and deﬁne E(Ti ) to be the set of all pairs v v ′ such that v = (v0 , . . . , vk ) and v ′ =
(v0 , . . . , vk , vk+1 ). The root of Ti is (v0 ) where v0 is the root of Hi′ . It is easy to check that
|V (Ti )| ≤ (2d + 1)h+1 .
For a sequence of vertices v = (v1 , . . . , vk ) let last(v) = vk be the last entry of the tuple
′
v. Let χi : V (Ti ) → N be the coloring deﬁned by χ′i (v) = 1 for all v where last(v) ∈ Vi ,
χ′i (v) = 2 for all v where last(v) ∈ V (Hi′ ) \ V (Hi ), χ′i (v) = 3 + χi (last(v)) for all v where
last(v) ∈ Si , and χ′i (v) = 0 for all other tuples. Let Γi := Aut(Ti , χ′i ). Also let γ1→2 be an
isomorphism from (T1 , χ′1 ) to (T2 , χ′2 ) (if no such isomorphism exists then Iso(I) = ∅ and
we are done).
Let Ai = {v ∈ V (Ti ) | last(v) ∈ V (Hi′ ) \ V (Hi )}. Note that every element v ∈ Ai is
a leaf of Ti . Also note that Ai is invariant under Γi , that is, Aγi = Ai for all γ ∈ Γi . For
v ∈ Ai let par(v) be the parent node of v in the tree Ti . Observe that last(par(v)) ∈ Si for
every v ∈ Ai . Let Bi = {par(v) | v ∈ Ai }. For w ∈ Bi let Ai (w) = {v ∈ Ai | par(v) = w}
and let A∗i (w) = {last(v) | v ∈ Ai (w)} = {S} × S where S = last(w).
Now let γ ∈ Γ1 γ1→2 be an isomorphism from (T1 , χ′1 ) to (T2 , χ′2 ). Then, for every
w ∈ B1 the isomorphism γ induces a bijection γ w : last(w) → last(w γ ) which is induced
by how γ maps A1 (w) to A2 (w γ ). Now let
′
Γ′1 γ1→2
= {γ ∈ Γ1 γ1→2 | ∀w ∈ B1 : γ w ∈ Θlast(w) τlast(w),last(wγ ) }.

16

Observe that the set indeed forms a coset due to property (N). Moreover, a representa′
tion for Γ′1 γ1→2
can be computed in time polynomial in |V (T1 )| since the group Γ1 acts
independently as a symmetric group on all the sets A1 (w).
Observe that, up to now, we have not enforced any consistency between the maps
w
γ . Indeed, there may be elements w, w ′ ∈ B1 such that last(w) = last(w ′ ) but γ w 6=
′
γ w . To ﬁnish the proof we need to enforce such a consistency property. Then every
′
that fulﬁlls the consistency property naturally translates back to
isomorphism γ ∈ Γ′1 γ1→2
an isomorphism of I.
For v ∈ V (Hi′ ) we deﬁne the label ℓ(v) = v if v ∈ V (Hi ) and ℓ(v) = w if v =
(S, w) ∈ V (Hi′ ) \ V (Hi ). Also we deﬁne colorings Ci : L(Ti )2 → N in such a way that for
all v = (v0 , . . . , vk ), v ′ = (v0′ , . . . , vk′ ′ ) ∈ L(Ti ), w = (w0 , . . . , wℓ ), w ′ = (w0′ , . . . , wℓ′ ′ ) ∈ L(Tj )
Ci (v, v ′ ) = Cj (w, w ′ ) ⇐⇒ k = ℓ and k′ = ℓ′
′

and ∀i ∈ [k], j ∈ [k ] : ℓ(vi ) =

ℓ(vj′ )
′

⇐⇒ ℓ(wi ) =



ℓ(wj′ )

′

and v ∈ Ai ⇐⇒ w ∈ Aj and v ∈ Ai ⇐⇒ w ∈ Aj .

(1)
(2)
(3)

Now let
∗
′
Γ∗1 γ1→2
= {γ ∈ Γ′1 γ1→2
| (T1 , C1 )γ = (T2 , C2 )}.
c

By Theorem 12 a representation for this coset can be computed in time 2O(h·log d) for some
∗
naturally deﬁnes an isomorphism of I and
comstant c. We claim that every γ ∈ Γ∗1 γ1→2
conversely, every isomorphism of I can be described like this. Let Vi′ = {v ∈ V (Ti ) |
∗
. Then
last(v) ∈ Vi }. Let v, v ′ ∈ Vi′ such that last(v) = last(v ′ ) and let γ ∈ Γ∗1 γ1→2
∗
γ
′
γ
last(v ) = last((v ) ) by property (2) and (3) of the colorings Ci . Hence, every γ ∈ Γ∗1 γ1→2
V
1
naturally deﬁnes a bijection γ : V1 → V2 .
∗
Additionally, for v ∈ Ai and v ′ ∈ Vi′ such that ℓ(last(v)) = last(v ′ ) and γ ∈ Γ∗1 γ1→2
it holds that last(v γ ) = last((v ′ )γ ) by the same argument. With this, we obtain that
γ V1 is indeed an isomorphism of I. The hyperedges S1 and S2 are encoded in the tree
structure (and they have to be mapped to each other by the coloring χ′i ) and the coloring
of hyperedges is encoded in the coloring χ′i which has to be preserved. Also, when mapping
an element w ∈ B1 to another element w γ ∈ B2 the children have to mapped to each other
in such a way that the corresponding bijection lies in the corresponding coset. So overall
γ V1 is an isomorphism of I.
On the other hand, every isomorphism ϕ ∈ Iso(I) extends naturally to an isomorphism
from H1 to H2 and thus, it also extends to an isomorphism from H1′ to H2′ and from T1 to
T2 , since all relevant objects are deﬁned in an isomorphism-invariant way. Hence, from a
∗
we can easily compute a representation for Iso(I).
representation for Γ∗1 γ1→2
Looking at the properties of the tree decompositions computed in Theorem 6 and 9 we
have for every node t that either the adhesion sets to the children are all equal or they are
all distinct. Up to this point we have only considered the problem that all adhesion sets

17

are distinct (i.e. the coset-hypergraph-isomorphism problem). Next we consider the case
that all adhesion sets are equal. Towards this end we deﬁne the following variant.
An instance of multiple-colored-coset-isomorphism is a 6-tuple I = (V1 , V2 , χ1 , χ2 , F, f)
such that
1. χi : [t] → N is a coloring,
2. F = {Θi ≤ Sym(V ) | i ∈ [t]}, and
3. f = {τi,j : V1 → V2 | i, j ∈ [t] such that χ1 (i) = χ2 (j)} such that
(a) every τi,j ∈ f is bijective, and
−1
′
(b) for every color i ∈ N and every j1 , j1′ ∈ χ−1
1 (i) and j2 , j2 ∈ χ2 (i) and θ ∈
′
Θj1 , θ ∈ Θj1′ it holds that
′
θτj1,j2 τj−1
′ ,j θ τj ′ ,j ′ ∈ Θj1 τj ′ ,j2 .
1
1 2
2
1

(N2)

The instance is solvable if there is a bijective mapping ϕ : V1 → V2 and a π ∈ Sym(t) such
that
1. χ1 (i) = χ2 (π(i)) for all i ∈ [t], and
2. for every i ∈ [t] it holds that ϕ ∈ Θi τi,π(i) .
The set Iso(I) is deﬁned analogously.
Lemma 13. Let I = (V1 , V2 , χ1 , χ2 , F, f) be an instance of multiple-colored-coset-isomorphism. Then a representation for the set Iso(I) can be computed in time
min((|V1 |!|F|)O(1) , |F|!O(1) 2O(log

c

(|V1 |))

)

for some constant c.
Proof. The ﬁrst run time can be achieved by brute force in the following way. We iterate
through all ϕ : V1 → V2 and check in polynomial time if a π ∈ Sym(t) exists that satisﬁes
(1) and (2). (This can be done by computing, for every i ∈ [t], the set Ai of those j ∈ [t]
such that ϕ ∈ Θi τi,j . Then one needs to ﬁnd a permutation π ∈ Sym(t) such that π(i) ∈ Ai
for all i ∈ [t]. This can be interpreted as a matching problem.) The results is the union of
all these ϕ.
However, for the second run time we iterate through all π ∈ Sym(t) satisfying (1)
and compute all corresponding ϕ : V1 → V2 satisfying
S (2) which in turnTcan be done
by iterated coset-intersection. The result is Iso(I) = π∈Sym(t) satisfying (1) i∈[t] Θi τi,π(i) .
Coset-intersection can be done in quasi-polynomial time [Bab16].

18

6

The isomorphism algorithm

Lemma 14. Let G = (D, E) be a graph of tree width at most k and let H be a rooted graph
such that D ⊆ V (H). Then, one can compute an isomorphism-invariant rooted graph H ′
such that
1. H is an induced subgraph of H ′ ,
2. fdegH ′ (w) ≤ max{d, k + 1} + 1 for all w ∈ V (H ′ ) where d = maxw∈V (H) fdegH (w),
3. depth(H ′ ) ≤ depth(H) + k + 2, and
4. for every clique C ⊆ D there is a corresponding vertex C ∈ V (H ′ )
in time 2O(k) · |V (H)|O(1) .
Here, isomorphism invariant means that every isomorphism ϕ ∈ Iso(H1 , H2 ), which
naturally restricts to an isomorphism from G1 to G2 , can be extended to an isomorphism
from H1′ to H2′ .
Proof. Let G(0) = G and for i > 0 let G(i) = G(i−1) [V (i) ] where V (i) = {v ∈ V (G(i−1) ) |
degG(i−1) (v) > k}. Since G has tree width at most k it follows that there is some i∗ > 0
∗
such that G(i ) is the empty graph. For every clique C ⊆ D we deﬁne i(C) to be the
maximal i ∈ N such that C ⊆ V (G(i) ). Moreover, let a(C) = C \ V (G(i(C)+1) ). Observe
that a(C) 6= ∅ and for every v ∈ a(C) it holds degG(i(C)) (v) ≤ k and C ⊆ NG(i(C)) [v].
For v ∈ D let i(v) be the maximal i ∈ N such that v ∈ V (G(i) ). Let A(v) = NG(i(v)) [v].
Note that |A(v)| ≤ k + 1.
For a set S we deﬁne the rooted graph LS to be the graph associated with the subset
lattice of S, that is, LS = (Pow(S), ES , ∅) where AB ∈ ES if A ⊆ B and |B \ A| = 1. Now
let H ′ be the following graph. For every v ∈ D we attach the graph LA(v) to the vertex
v ∈ V (H), that is, the root node ∅ ∈ V (LA(v) ) is connected to the vertex v. It can be
easily veriﬁed that H ′ satisﬁes all requirements. Observe that C ⊆ A(v) for every v ∈ a(C)
where C is a clique of G.
Theorem 15. Let k ∈ N and let G1 , G2 be connected graphs. There is an algorithm that
either correctly concludes that tw(G1 ) > k, or computes the set of isomorphisms Iso(G1 , G2 )
c
in time 2O(k log k) |V (G)|O(1) .
Proof. We describe a dynamic programming algorithm A that has an input (I1 , I2 ) where
Ij = (Gj , Sj , Tj , βj , ηj ) where Gj is a graph, (Tj , βj ) is a tree decomposition of the graph,
Sj ⊆ V (Gj ) is a subset of the vertices contained in the root bag, and ηj is a (partial)
function that assigns nodes tj ∈ V (Tj ) a graph η(tj ) which is isomorphism invariant w.r.t
Tj,tj , βj,tj , Gj,tj and Sj,tj as in remark 10. The isomorphisms Iso(I1 , I2 ) are all isomorphisms ϕ : V (G1 ) → V (G2 ) from (G1 , S1 ) to (G2 , S2 ) for which there is a bijection between the nodes of the trees π : V (T1 ) → V (T2 ) such that for all t ∈ V (T1 ) we have that
19

ϕ(β1 (t)) = β2 (π(t)). The algorithm computes a coset A(I1 , I2 ) = Iso(I1 , I2 ). In our recursive procedure we maintain the following properties of the tree decomposition for each
unlabeled bag βj (tj ) (ηj (tj ) = ⊥).
(U1) The graph Gkj [βj (tj )] is clique- (U2) Each adhesion set of tj and also S are
cliques in Gkj .
separator free, and
And for each labeled bag βj (tj ) we require the following.
(L1) The cardinality |βj (tj )| is bounded (L3) For each bag βj (tj ) the adhesion sets of
by cL ,
the children are all equal to βj (tj ) or
the adhesion sets of the children are all
(L2) ηj (tj ) = H is a connected rooted
distinct,
graph such that βj (tj ) ∪ βj (tj )2 ⊆
V (H) and for each adhesion set (L4) If the adhesion sets are all equal and
S there is a corresponding vertex
βj (tj ) is no clique in Gkj , then the carS ∈ V (H), depth(H) ∈ O(k) and
dinality |βj (tj )| is bounded by cM and
O(1)
fdeg(v) ∈ k
for all v ∈ H,
the number of children of tj is bounded
by k.
The initial input of A consists of the graphs G1 , G2 together with their canonical (unlabeled) clique separator decompositions (Tj , βj ) of their k-improved graphs Gkj from Theorem 6. For Sj we choose the empty set. Since the clique separator decomposition is
canonical we have Iso(I1 , I2 ) = Iso(G1 , G2 ) and therefore the algorithm computes all isomorphisms between G1 and G2 .
Description of A:
For j = 1, 2 let tj1 , . . . , tjℓ be the children of tj and let (Tji , βji , ηji ) be the decomposition
of the subtree rooted at tji . Let Gji be the graph corresponding to (Tji , βji , ηji ). Let
Vji := V (Gji ) and let Sji := βj (tj ) ∩ Vji be the adhesion sets of the children, let Zji be
Vji \ Sji , and let Iji := (Gji , Sji , Tji , βji , ηji ). We assume that the isomorphisms A(I1i , I2i′ )
have already been computed via dynamic programming.
We have to consider two cases depending on the root tj ∈ Tj .
Case βj (tj ) are both unlabeled: Let v1 be a vertex in β1 (t1 ) of degree at most k in Gk1 [β1 (t1 )]
and compute the canonical labeled tree decomposition (T1′ , β1′ , η1′ ) of (Gk1 [β1 (t1 )], v1 )
from Theorem 9. For each vertex v2 ∈ β2 (t2 ) of degree at most k in Gk2 [β2 (t2 )] we
compute the canonical labeled tree decomposition (T2′ , β2′ , η2′ ) of (Gk2 [β(t2 )], v2 ) from
Theorem 9. Notice that the bags of (Tj′ , βj′ , ηj′ ) satisfy (L1)–(L4), because in the
case tw(Gj ) ≤ k, the k-improvement does not increase the tree width as seen in
Lemma 5(2). Notice that the adhesion sets Sji and Sj are cliques in Gkj and these
cliques must be completely contained in one bag. We attach the children (Tji , βji , ηji )
to (Tj′ , βj′ , ηj′ ) by adding them to the highest possible bag and we choose a new root
20

as the highest possible node rj ∈ V (Tj′ ) such that Sj ⊆ βj′ (rj ). By doing this, we
obtain (Tj′′ , βj′′ , ηj′′ ). We need to recompute ηj′′ (sj ) for all nodes sj ∈ V (Tj ) where new
children are attached to preserve Property (L2). We call the algorithm in Lemma 14
with the input Gj [βj (sj )], ηj′′ (sj ) and obtain ηj′′′ (sj ). Finally, we obtain (Tj′′ , βj′′ , ηj′′′ )
and deﬁne Ij′ := (G, S, Tj′′ , βj′′ , ηj′′′ ). We show that (L1)-(L4) remains satisﬁed. By
possibly introducing new bags we can preserve Property (L3): The adhesion sets are
either pairwise diﬀerent or all equal. We can preserve Property (L4). Consider a
bag sj in which all adhesion sets are equal and where βj′′ (sj ) is not a clique in Gkj .
Then the children are not any of the attached children tj1 , . . . , tjℓ and therefore the
number of children of sj remains bounded by cM .
′
′
For each of the vertices v2 ∈ β2 (t2 ) we compute the isomorphisms
S A(I1 , I2 (v2′ )) ′recursively. We return the smallest coset that contains the union v2 ∈β2 (t2 ) Iso(I1 , I2 (v2 )).

Case βj (tj ) are both labeled: We consider two cases depending whether the adhesion sets
of tj are all diﬀerent or not.
If all adhesion sets are diﬀerent, we use the algorithm from Lemma 11 as follows.
We encode the isomorphism problem Iso(I1 , I2 ) as an instance of coset-hypergraphisomorphism. First, we encode the tree decomposition as
I = (β1 (t1 ), β2 (t2 ), {S1i }, {S2i }, χ1 , χ2 , F, f)

and H1 = η1 (t1 ), H2 = η2 (t2 ) where F, f are the isomorphisms between the children of
t1 and the children of t2 restricted to their adhesion sets. We can easily construct F, f
with the isomorphisms A(I1i , I2i′ )|S1i that have already been computed. The colorings
χi are deﬁned as follows. Two S1i and S2i′ get assigned the same color (i.e. χ1 (S1i ) =
χ2 (S2i′ )) if and only if the set of isomorphisms A(I1i , I2i′ ) is not empty. Since F, f
consist of isomorphisms the consistency property N is satisﬁed. Next, we encode the
edge relation of edges contained in the root bag as I ′ = (β1 (t1 ), β2 (t2 ), E(β(t1 )) ∪
{S1 }, E(β(t2 )) ∪ {S2 }, χ′1 , χ′2 , F ′ , f′ ). To construct F ′ , f′ we deﬁne for all edges e1 ∈
E(β1 (t1 )), e2 ∈ E(β2 (t2 )) the allowed isomorphisms Θe1 τe1 ,e2 as the set of bijections
between β1 (t1 ) and β2 (t1 ) that map e1 to e2 . Moreover, the allowed isomorphisms
ΘS1 τS1 ,S2 is the set of bijections between β1 (t1 ) and β2 (t1 ) that map S1 to S2 . We
deﬁne χ1 , χ2 as a coloring mapping all edges to the integer 0 and mapping S1 and
S2 to the integer 1. Finally, we combine both instances I and I ′ to obtain I ′′ and
compute the isomorphisms Iso(I ′′ ) by the algorithm in Lemma 11. We extend the
c ′′ ) := {ϕ : V1 → V2 |
isomorphisms to the whole graph and deﬁne and return Iso(I
′′
ϕ|β1 (t1 ) ∈ Iso(I ), ∃π ∈ Sym(ℓ) : ϕ|V1i ∈ Iso(I1i , I2π(i) )}.
If all adhesions sets are equal, the procedure is analogous, but we compute Iso(I ′′ )
by calling the algorithm from Lemma 13.

(Correctness.) We consider the ﬁrst case. Since each isomorphismSfrom I1 to I2 maps the
vertex v1 to some vertex v2 ∈ β2 (t2 ) we conclude that Iso(I1 , I2 ) = v2 ∈β2 (t2 ) Iso(I1′ , I2′ (v2 )).
21

c ′′ ). Let ϕ ∈ Iso(I1 , I2 )
We consider the second case. We show that Iso(I1 , I2 ) = Iso(I
be an isomorphism, i.e. ϕ is an isomorphism from (G1 , S1 ) to (G2 , S2 ) for which there is
a bijection between the nodes of the trees π : V (T1 ) → V (T2 ) such that for all t ∈ V (T1 )
we have that ϕ(β1 (t)) = β2 (π(t)). Equivalently, since each π maps the root of T1 to the
root of T2 we have that ϕ|β1 (t1 ) ∈ Iso(G1 [β1 (t1 )], S1 , G2 [β2 (t2 )], S2 ) and there is a bijection
π : Sym(ℓ) between the children of t1 and t2 such that ϕ|V (G1i ) ∈ Iso(I1i , I2π(i) ). The
condition ϕ|β1 (t1 ) ∈ Iso(G1 [β1 (t1 )], S1 , G2 [β2 (t2 )], S2 ) is equivalent to ϕ|β1 (t1 ) ∈ Iso(I ′ ).
c ′′ ).
Therefore, ϕ ∈ Iso(I1 , I2 ), if and only if ϕ ∈ Iso(I

(Running time.) Due to dynamic programming the number of calls is polynomial in |V (G)|.
More precisely, for each bag of the clique separator decomposition, we construct a labeled
tree decomposition and both have polynomially many bags.
Consider the ﬁrst case. The construction of the labeled tree decomposition from Theorem 9 takes time 2O(k log k) |V (G)|O(1) . Updating the graph H = ηj′′ (sj ) in the case where the
clique separators where attached is done by Lemma 14 in time 2O(k log k) |V (H)|O(1) . Notice
that the depth of H is bounded by O(k) and the maximum forward-degree is bounded by
kO(1) . Therefore this gives a bound on the number of vertices |V (H)| ∈ 2O(k log k) .
Consider the second case in which all adhesion sets are diﬀerent. The isomorphism subc
routine in Lemma 11 runs in time 2O(k·log k) . Notice that for given Iso(I ′′ ) and Iso(I1i , I2i′ )
c ′′ ) can be constructed in polynomial time, since for each isomorphism
the coset Iso(I
ϕ′′ ∈ Iso(I ′′ ) there is already a unique π ∈ Sym(ℓ) such that ϕ′′ |S1i ∈ Iso(I1i , I2π(i) )|S1i
and therefore it suﬃces to extend ϕ using generators for Iso(I1i , I2π(i) ).
Next, consider the second case in which all adhesion sets are equal. Assume that βj (tj )
is not a clique in Gkj . Then by Property (L4) the cardinality |βj (tj )| is bounded by cM
and the number of children of tj is bounded by k. In this case we have that |F| ≤ k for
c
our subroutine which leads to a run time |F|!O(1) 2O(log (|β1 (t1 )|)) ⊆ 2O(k log k) . In the case
where βj (tj ) is a clique in Gkj we have that |βj (tj )| ≤ k + 1 and |F| ≤ |V (Gj )|. This leads
to a run time of (|V1 |!|F|)O(1) ⊆ 2O(k log k) |V (G1 )|O(1) . It remains to explain how the coset
c ′′ ) can be constructed in polynomial time. The cosets are colored according to the
Iso(I
isomorphism types of the graphs Gji which ensures property N2. Let P = P1 ∪· . . . ∪· Pp be
a partition of [ℓ] into isomorphism classes, i.e. i, j ∈ Ps if and only if Θi τi,k = Θj τj,k for
some (and due to property N2 for all) k ∈ [ℓ]. Now, for each isomorphism ϕ′′ ∈ Iso(I ′′ )
there is a unique coset Π of Sym(P1 ) × . . . × Sym(Pp ) such that ϕ′′ ∈ Iso(I1i , I2π(i) )|β1 (t1 )
for all π ∈ Π and therefore it suﬃces to extend ϕ using generators for Iso(I1i , I2π(i) ) and
Π.

7

Canonization

In this section we adapt our techniques to obtain an algorithm which computes a canonization for a given graph of tree width at most k. Since Babai’s quasi-polynomial time

22

algorithm [Bab16] only tests isomorphism of two given input graphs and can not be used
for canonization purposes, our canonization algorithm has a slightly worse running time.
However, our canonization algorithm still signiﬁcantly improves on the previous best due
to Lokshtanov, Pilipczuk, Pilipczuk, and Saurabh [LPPS17].
One of the main tasks for building the canonization algorithm out of our isomorphism
test is to adapt Lemma 11. To achieve this we shall use several group theoretic algorithms
concerned with canonization. We start by giving the necessary background.

7.1

Background on canonization with labeling cosets

Two graphs graphs G and H are called isomorphic with respect to a group ∆ ≤ Sym(V (G)),
if there is a bijection δ ∈ ∆ such that Gδ = H. In this case we write G ∼
=∆ H. By Aut∆ (G)
we denote the automorphism group of a graph G restricted to ∆, i.e., all δ ∈ ∆ such that
Gδ = G.
In the following let X denote a class of graphs, closed under isomorphisms.
Definition 16. Assume that V = {1, . . . , |V |}. A function CF∆ : X → X is a canonical
form with respect to a group ∆ ≤ Sym(V ) for a graph class X , if CF∆ (G) ∼
=∆ G for all
∼
G ∈ X , and if G =∆ H implies CF∆ (G) = CF∆ (H) for all G, H ∈ X .
Definition 17. Assume that V = {1, . . . , |V |}. The canonical labelings of a graph G with
respect to a group ∆ ≤ Sym(V (G)) are the elements in ∆ that bring G in the canonical
form, i.e., CL(G; ∆) := {δ ∈ ∆ | Gδ = CF∆ (G)}.
For the purpose of recursion, it is usually more convenient to compute the entire coset
of canonical labelings rather than just a canonical form.
Lemma 18 ([BL83]). Assume that V = {1, . . . , |V |}. The following three conditions characterize canonical labelings.
(CL1) CL(G; ∆) ⊆ ∆,
(CL2) CL(G; ∆) = δ CL(Gδ ; ∆) for all δ ∈ ∆, and
(CL3) CL(G; ∆) = Aut∆ (G)π for some (and thus for all) π ∈ CL(G; ∆).
These conditions imply that the assignment of Gπ for an arbitrary π ∈ CL(G; ∆) is
independent of the choice of π and that Gπ is a canonical form of G with respect to ∆,
justifying the name.
Above we made the assumption that V is a ﬁxed linearly ordered set. We can drop
this assumption and can deﬁne canonical labelings for arbitrary vertex sets as seen next.
For a labeling coset τ ∆ ≤ Label(V (G)) we deﬁne CL(G; τ ∆) to be the set τ CL(Gτ ; ∆)
which is well deﬁned due to Property (CL2). In general, a canonical form CF for a graph G
over an arbitrary (not necessary ordered) vertex set V is a function such that CF(G) ∼
=G
23

for all G ∈ X , and G ∼
= H implies CF(G) = CF(H) for all G, H ∈ X . Notice that Gπ
deﬁnes such a canonical form for some π ∈ CL(G; Label(V (G))). An algorithm to compute
CL(G; Label(V (G))) for a graph of tree width at most k will be present in the last section.
The composition-width of a coset τ ∆, denoted cw(τ ∆) is the smallest integer k ∈ N
e k , that is, every non-Abelian composition factor of ∆ is isomorphic to a
such that τ ∆ ∈ Γ
subgroup of Sym(k). The composition width of a collection of cosets cw(S) is the maximum
composition width among all elements of S. Let ω(n) be the smallest function such that,
if ∆ ≤ Sym(X) is primitive, then |∆| ≤ |X|ω(cw(∆)) .
Theorem 19 ([BL83]). Given a graph G and a labeling coset τ ∆ ∈ Label(V ), a canonical
labeling coset CL(G; τ ∆) can be computed in time |V (G)|O(ω(cw(∆))) .
It is actually known that ω(n) ∈ O(n) as stated in [BKL83], see [LS99]. Analogously,
for a hypergraph X we ﬁrst deﬁne the canonical labelings with respect to a group and a
start segment of N as the vertex set. Meaning CL(X; ∆) satisﬁes (CL1)-(CL3) with X in
place of G. Then for graphs on arbitrary vertex set and a given labeling coset we deﬁne
CL(X; ρ∆) to be the set ρ CL(X ρ ; ∆).
Theorem 20 ([Mil83], see [Pon91]). Given a hypergraph X = (V, E) and a labeling
coset τ ∆ ∈ Label(V ), a canonical labeling coset CL(X; τ ∆) can be computed in time
(|V (X)||E(X)|)O(ω(cw(∆))) .
We describe several polynomial time operations that can used in general when dealing
with labeling cosets of a set of natural numbers.
We ﬁrst deﬁne an ordering on Label({1, . . . , n}) = Sym({1, . . . , n}). For two such
permutations π1 , π2 deﬁne π1 ≺ π2 if there is an i ∈ {1, . . . , n} such that π1 (i) < π2 (i)
and π1 (j) = π2 (j) for all 1 ≤ j < i. We extend the deﬁnition to labeling cosets of {1, . . . , n}
as follows. Suppose τ1 Θ1 , τ2 Θ2 ≤ Label({1, . . . , n}) are labeling cosets. Then we deﬁne τ1 Θ1 ≺ τ2 Θ2 if |τ1 Θ1 | < |τ2 Θ2 | or if |τ1 Θ1 | = |τ2 Θ2 | and the smallest element of τ1 Θ1 \
τ2 Θ2 is smaller (w.r.t. to ≺ on permutations) than the smallest element of τ2 Θ2 \ τ1 Θ1 .
Let τ1 , τ2 , . . . , τt be a set of bijections with the same domain and range. We denote by
hτ1 , τ2 , . . . , τt i
the smallest coset containing all τi . This coset can be computed in polynomial time (see
for example Lemma 16 of the arXiv version of [GS15]).
Lemma 21. There is a polynomial time algorithm that, given a labeling coset τ Θ of the
set {1, . . . , n}, as τ and a generating set S of Θ, computes a sequence of at most n log n
elements (τ1 , τ2 , . . . , τt ) of τ Θ such that
1. τ Θ = hτ1 , . . . , τt i,
2. τi is the smallest element of τ Θ not contained in hτ1 , . . . , τi−1 i, and
24

3. the output of the algorithm only depends on τ Θ (and not on τ or S).
Proof. It suﬃces to ﬁnd a solution for the following task: Given τ1 , τ2 , . . . , τℓ ﬁnd the
smallest element in τ Θ not contained hτ1 , τ2 , . . . , τℓ i.
This task can be solved in polynomial time as follows. We ﬁnd the smallest j such that
not all elements of τ Θ have the same image of j. Otherwise, if each element of τ Θ has the
same image, then τ Θ consists of only one element and we are done. With standard group
theoretic techniques, including the Schreier-Sims algorithm, we can compute the possible
images of j under τ Θ, say i1 , i2 , . . . , ik . For each m ∈ {1, . . . , k} we compute (τ Θ)j7→im , the
set of those elements in τ Θ that map j to im . Notice that if τ Θ contains an element not in
hτ1 , τ2 , . . . , τℓ i, then there is also a (τ Θ)j7→im that contains an element not in hτ1 , τ2 , . . . , τℓ i.
We ﬁnd the smallest im such that (τ Θ)j7→im is not contained in hτ1 , τ2 , . . . , τℓ i. Now we
compute (hτ1 , τ2 , . . . , τℓ i)j7→im and recurse with (τ Θ)j7→im .
Each of the operations can be performed in polynomial time with standard techniques
(see [GS15, Beginning of Section 9], for a detailed exposition, the reader can refer to an
arXiv version of the paper).
Note that the lemma can be used to compute canonical generating sets of a permutation
group deﬁned on a linearly ordered set.
Corollary 22.
1. Given a labeling coset τ Θ of {1, . . . , n} we can compute the smallest
element (w.r.t. “≺”) in time polynomial in n.
2. Given a collection of labeling cosets {τ1 Θ1 , . . . , τt Θt } of {1, . . . , n} via generating sets,
we can compute their order (w.r.t. “≺”) in time polynomial in t and n.

7.2

Graphs with coset-labeled hyperedges

With the results establiched in the previous subsection we can now give a variant of Lemma
11 suitable for canonization. For this purpose we adapt the problem of coset-hypergraph
isomorphism to the context of computing canonical labelings. More precisely, we deﬁne a
new combinatorial object, namely hypergraphs with coset-labeled hyperedges, and canonical labelings for those objects.
A hypergraph with coset-labeled hyperedges is a 4-tuple (V, S, χ, F) consisting of
1. a vertex set V ,
2. the hyperedges S ⊆ Pow(V ) which form a collection of subsets of V ,
3. a coloring χ : S → N of the hyperedges, and
4. a collection F = {τS ΘS ≤ Label(S) | S ∈ S} of labeling cosets of the hyperedges
(that is, for each S the collection contains a coset τS ΘS ) which satisﬁes ΘS = ΘS ′
for all S, S ′ ∈ S with χ(S) = χ(S ′ )).
25

For a map ϕ : V → V ′ we deﬁne (V, S, χ, F)ϕ to be the tuple (V ϕ , S ϕ , χϕ , F ϕ ),
where S ϕ = {S ϕ | S ∈ S}, χϕ = ϕ−1 χ and F ϕ is the collection {ϕ−1 τS ΘS }. The automorphism group of a hypergraph with coset-labeled hyperedges X with respect to a
group ∆ ≤ Sym(V (X)), written Aut∆ (X), are all permutations δ ∈ ∆ such that X δ = X.
Now, we adapt the canonization to our combinatorial object and deﬁne canonical labeling for hypergraphs with coset-labeled hyperedges. As before, we assume that V (X) =
{1, . . . , |V (X)|}. A canonical labeling is a map that assigns every pair consisting of a hypergraph with coset-labeled hyperedges X and a group ∆ ≤ Sym(|V |) a labeling coset
CL(X; ∆) such that
(CL1) CL(X; ∆) ⊆ ∆,
(CL2) CL(X; ∆) = δ CL(X δ ; ∆) for all δ ∈ ∆, and
(CL3) CL(X; ∆) = Aut∆ (X)π for some (and thus for all) π ∈ CL(X; ∆).
As before, we extend the canonical labelings to arbitrary (not necessary ordered) vertex
sets. For a labeling coset τ ∆ ≤ Label(V ) we write CL(X; τ ∆) for τ CL(X τ ; ∆). This is
well deﬁned due to Property (CL2).
We are now ready to formulate the analogue of Lemma 11 for the canonization algorithm.
Lemma 23. There is an algorithm that computes a canonical labeling of a pair (X; τ ∆)
consisting of a hypergraph with coset-labeled hyperedges X = (V, S, χ, F) and a labeling
coset τ ∆ ≤ Label(V ) which has a running time of (|V (X)||S|)O(max{cw(∆),cw(F )}) .
Proof. Since CL(X; τ ∆) is τ CL(X τ ; ∆) by deﬁnition, we need to give an algorithm for
given a pair (X; ∆) with X = (V, S, χ, F) that computes CL(X; ∆). If ∆ does not preserve S and χ, we proceed as follows. Using Theorem 20 we compute a canonical labeling coset τ ∆′ = CL((V, S, χ); ∆) of the hypergraph so that ∆′ preserves S τ and χτ .
We compute and return CL(X; τ ∆′ ) recursively (Notice that CL(X; τ ∆′ ) is deﬁned as
τ CL(X τ ; ∆′ )).
So we can assume in the following that ∆ preserves S and χ, i.e, S δ = S and χδ = χ
for all δ ∈ ∆. Let U be the set of pairs {(S, s) | S ∈ S, s ∈ S}. We can think of U as the
disjoint union of all sets S ∈ S. For notational convenience we deﬁne US := {S} × S.
b on the disjoint union V ∪ U . Roughly speaking, we deﬁne
Next we deﬁne a labeling ∆
a labeling on V ∪ U that orders V according to a δ ∈ ∆ and orders the sets US according
to the ordering of the sets S δ . Inside the set US the vertices are ordered according to
b to be the labeling of V ∪ U consisting of the
some ρS ∈ τS ΘS . More formally, we deﬁne ∆
b
labelings δ for which there are ρS ∈ τS ΘS .
b V = δ for some element of δ ∈ ∆,
1. δ|
b

b

2. (S, s)δ < (S ′ , s′ )δ if S δ ≺ S ′δ (the ordering ≺ of subsets of N as deﬁned in the
preliminaries), and
26

b

b

3. (S, s)δ < (S, s′ )δ if sρS < s′ρS .
b is a labeling coset of the set V ∪ U and has composition-width at most
The coset ∆
max{cw(∆), cw(S)}.
Consider the bipartite graph Y deﬁned on V ∪U by connecting v and (S, v) for each S ∈
S for which v ∈ S. Return the canonical labeling coset of the graph Y restricted to V , i.e.,
b V.
CL(Y ; ∆)|
b restricted to V is a canonical labeling coset
(Canonical labeling.) We argue that CL(Y ; ∆)
of (X; ∆).
b restricted to V are in ∆.
(CL1) By deﬁnition, all elements of ∆
(CL2) We consider the result of applying the algorithm to (X δ ; ∆) for any δ ∈ ∆. In
the case that ∆ does not preserve S and χ, the algorithm returns δ−1 τ ∆′ . So assume that
∆ preserves S and χ already, In this case the deﬁnition of V ∪ U remains unchanged since
b the algorithm computes ∆
b δ . In Place of Y the algorithm
∆ preserve S. In place of ∆,
δ
b δ )|V = δ−1 CL(Y ; ∆)|
b V.
computes Y . But then the result of the computation is CL(Y δ ; ∆
′
′
′
b
b
b
b
b
(CL3) Suppose δ, δ ∈ CL(Y ; ∆) and δ|V = δ and δ |V = δ . We need to show that δδ′−1
is an automorphism of X. Since δ, δ ∈ ∆, it is clear that δδ′−1 preserves S and χ. It remains
to show that δδ′−1 is compatible with F. In other words, we need to show that F δ =
′
{δ−1 τS ΘS | S ∈ S} and F δ = {δ′ −1 τS ΘS | S ∈ S} are actually the same set.
′
Choose S ∈ S. Let S ′ be the element of S for which S δ = S ′δ . Such an element exists
and is unique. Since χ is preserved we have ΘS = ΘS ′ and therefore it suﬃces to show
that δ−1 τS ΘS = δ′−1 τS ′ ΘS .
b
b
b
b′
Consider the graph Y δ = Y δ . Let γS be the map from S δ to (US )δ that maps each v δ ∈
′
b′
b
b
S δ to (S, v)δ . Similarly let γS′ ′ be the map from S ′ to (US ′ )δ = (US )δ that maps each v δ ∈
′
b′
b
b
S ′δ to (S ′ , v)δ . In the graph Y δ , for s ∈ S δ we have that sγS is the only vertex in (US )δ
′
b′
b
b′
that is a neighbor of s. Similarly, in Y δ = Y δ , we have that sγS ′ is the only vertex in (US ′ )δ
that is a neighbor of s. It follows that γS = γS′ ′ .
b we know that δγS = ρS + m for some ρS ∈ τS ΘS and some integer
By construction of ∆
′
′
′
m. Similarly δ γS ′ = ρS ′ + m′ for some ρ′S ′ ∈ τS′ ′ ΘS ′ and some integer m. In fact, it must
b′
b
′−1 =
be the case that m = m′ since (US ′ )δ = (US )δ . We conclude that δδ′−1 = δγS γS′−1
′ δ
′−1
′−1
′
ρS ρS ′ . Therefore δδ τS ′ ΘS = τS ΘS as desired.
(Running time.) We use two subroutines throughout the algorithm. The ﬁrst one is
Miller’s canonization algorithm for hypergraphs from Theorem 20 which runs in time
(|V ||S|)O(cw(∆)) . The second one is a canonization algorithm for the graph Y which runs
in time (|V | + |V ||S|)O(max{cw(∆),cw(S)}) .
We also need a second combinatorial subproblem that handles the case when V is small
but the family F is possibly large (this is analogue to multiple-colored-coset-isomorphism
and Lemma 13).
A set with multiple colored labeling cosets is a tuple (V, F, χ) consisting of
27

1. a vertex set V ,
2. a collection F = {τ1 Θ1 , τ2 Θ2 , . . . , τt Θt } of labeling cosets of V , and
3. a coloring χ : {1, . . . , t} → N assigning to every labeling coset in F a positive integer.
For a map ϕ : V → V ′ we deﬁne (V, F, χ)ϕ analogously to before. Similarly the
automorphism and canonical labelings of (V, F, χ) are deﬁned analogously to above.
We are now ready to formulate a lemma that is the analogue of Lemma 11, but with a
weaker run time since Babai’s quasi-polynomial time result does not lead to canonization
yet.
Lemma 24. There is an algorithm that computes a canonical labeling of a pair (X; τ ∆)
consisting of a set with multiple colored labeling cosets X = (V, F, χ) and a labeling coset
τ ∆ ≤ Label(V ) which has a running time of (|V |!|F|)O(1) .
Proof. Since CL(X; τ ∆) is τ CL(X τ ; ∆) by deﬁnition, we need to give an algorithm that
computes a canonical labeling for a given group ∆ ≤ Sym({1, . . . , |V |}) and a given set
with multiple colored labeling cosets on a ground set satisfying V = {1, . . . , |V |}. Let F =
{τ1 Θ1 , τ2 Θ2 , . . . , τt Θt } be the family of labeling cosets.
For each labeling δ ∈ ∆ we do the following. Consider the sets of the form δ−1 τi Θi . We
order these sets so that δ−1 τi Θi ≺χ δ−1 τj Θj if χ(τi Θi ) < χ(τj Θj ) or if χ(τi Θi ) = χ(τj Θj )
and δ−1 τi Θi ≺ δ−1 τj Θj , where ≺ is the ordering of coset labelings of {1, . . . , n} deﬁned in
Section 7. By Corollary 22 this ordering can be computed in polynomial time. For every δ
we get an ordered sequence δ−1 τi1 Θi1 , . . . , δ−1 τit Θit .
Let {δ1 , . . . , δs } be the collection of those δ for which this ordered sequence is lexicographically minimal. Then we let hδ1 , . . . , δs i be the output of the algorithm.
It follows from the construction that hδ1 , . . . , δs i satisﬁes the properties of a canonical
labeling coset.
By Corollary 22, for each δ the time requirement of the algorithm is polynomial in |F|
and |V |. There are at most |V |! many elements in ∆, and thus at most equally many
choices for δ, giving us the desired time bound.

7.3

The canonization algorithm

Finally, we have assembled all the tools to describe an algorithm that canonizes graphs of
bounded tree width.
Theorem 25. Let k ∈ N and let G be a connected graph. There is an algorithm that either
correctly concludes that tw(G) > k, or computes a canonical labeling coset CL(G; Label(V ))
2
in time 2O(k log k) |V (G)|O(1) .
We remark that the algorithm is closely related to the one described in Theorem 15. In
the isomorphism-algorithm the graph η(t) serves as a tool to exploit the structure of each
28

bag t. As the isomorphism-techniques depend on Babai’s quasi-polynomial time result
which does not extend to canonization yet, we will now use the fact that additionally
each bag can be guarded with a labeling coset α(t) of bounded composition-width. The
labeling coset α(t) serves a tool for eﬃcient canonization. The main change of the algorithm
therefore arises in (L2).
Proof. We describe a dynamic programming algorithm A with input I = (G, S, T, β, α)
where (T, β) is a tree decomposition of a graph G and S ⊆ V (G) is a subset of the vertices
contained in the root bag, and α is a (partial) function that maps nodes t ∈ V (T ) to
labeling cosets α(t) ≤ Label(β(t)). The algorithm computes a labeling coset A(I) such
that
(CL1) A(I) ≤ Label(V (G)) and A(I)|S ≤ Label(S), and
(CL2) A(I) = τ A(I τ ) for all τ ∈ Label(V (G)), and
(CL3) Aut(G, S, T, β, α)π ⊆ A(I) ⊆ Aut(G)π for some (and thus for all) π ∈ A(I).
In our recursive procedure we maintain the following properties of the tree decomposition for each unlabeled bag β(t) (α(t) = ⊥).
(U1) The graph Gk [β(t)] is clique- (U2) Each adhesion set of t and also S are
cliques in Gk .
separator free, and
For each labeled bag β(t) we require the following.
(L1) The cardinality |β(t)| is bounded (L3) For each bag β(t) the adhesion sets of
by cL ,
the children are all equal to β(t) or the
adhesion sets of the children are all dis(L2) The number of children of t is
tinct.
bounded by kc2L + 2k cL and α(t) ∈
e k+1 , and
(L4) If the adhesion sets are all equal, then
Γ
the cardinality |β(t)| is bounded by cM .
The initial input of A is the canonical clique separator decomposition (T, β) of the
k-improved graph Gk from Theorem 6. For S we choose the empty set. Since the clique
separator decomposition is canonical we have Aut(G, S, T, β, ⊥) = Aut(G) and therefore
the algorithm computes a canonical labeling coset of G.
Description of A:
Let t1 , . . . , tℓ be the children of t and let (Ti , βi , αi ) be the decomposition of the subtree
rooted at ti . Let Gi be the graph corresponding to (Ti , βi , αi ). Let Vi := V (Gi ), let
Si := β(t) ∩ Vi be the adhesion sets of the children, and let Zi be Vi \ Si . We assume that
the canonical labeling subcosets τi Θi := A(Gi , Si , Ti , βi , αi ) have already been computed
via dynamic programming.
29

We have to consider two cases depending on the root t ∈ T .
Case β(t) is unlabeled: For each vertex v ∈ β(t) of degree at most k in Gk [β(t)] we compute the canonical coset-labeled tree decomposition (T ′ , β ′ , α′ ) of (Gk [β(t)], v) from
Theorem 9. Notice that the bags of (T ′ , β ′ , α′ ) satisfy (L1)-(L4), because in the
case tw(G) ≤ k, the k-improvement does not increase the tree width as seen in
Lemma 5(2). Notice that the adhesion sets Si are cliques in Gk and these cliques
must be completely contained in one bag. We attach the children (Ti , βi , αi ) to
(T ′ , β ′ , α′ ) adding them to the highest possible bag and we choose a new root as
the highest possible node r ∈ V (T ′ ) such that S ⊆ β ′ (r). By doing this, we obtain
(T ′′ , β ′′ , α′′ ). We ensure Property (L2) because the number of children attached to
one bag can be bounded by the number of cliques in Gk that contains the bag. The
number of cliques again can be bounded by 2k cL which is a consequence of Lemma 14.
By possibly introducing new bags we can preserve Property (L3): The adhesion sets
are either pairwise diﬀerent or all equal. Since the adhesion sets Si are cliques in Gk
and therefore their size is bounded by k + 1, we also preserve Property (L4).
For each v we compute Θv := A(G, S, T ′′ , β ′′ , α′′ ) recursively. For each v we compute
the canonical form obtained by applying an arbitrary element of Θv to the graph.
Let M be those v for which the obtained canonized graph is minimal with respect
to lexicographic S
comparison of the adjacency matrix. Then we return the smallest
coset containing v∈M Θv .

Case β(t) is labeled: We apply Luks’ algorithm from Theorem 19 to get a subcoset that
respects the edge relation and get ψ ′ ∆′ := CL(G[β(t)]; α(t)). We apply Miller’s algorithm to get a subcoset that respects S and compute ψ∆ := CL((β(t), {S}); ψ ′ ∆′ ).

Compute a partial linear order on the graphs Gi by comparing the resulting adjacency matrices of Gτi i lexicographically (Notice that the order does no depend on
the representative τi ). Deﬁne χ : {S1 , . . . , Sℓ } → {1, . . . , h} according to this order
where h is the number of equivalence classes. We reﬁne χ such that χ(Si ) = χ(Sj )
implies Θi = Θj .
If all adhesion sets are diﬀerent, we compute a canonical labeling coset Λ of the
set β(t) by applying Lemma 23 to the input X = ((β(t), {Si }, {τi Θi |Si }, χ); ψ∆).
Otherwise, if all adhesion sets are equal, we compute Λ by applying the algorithm of
Lemma 24 to the input X = ((β(t), {τi Θi |β(t) }, χ); ψ∆). Notice that Property (CL1)
allows us to restrict τi Θi to Si .
We describe a canonical labeling coset of G.
For each λ ∈ Λ we deﬁne extensions to V (G) as follows. For each i we deﬁne τi′ Θ′i to
be the subcoset of those maps ρi ∈ τi Θi for which λ−1 ρi is minimal. (In fact, we have
to restrict these maps to ﬁt together (λ−1 |S λ )(ρi |Si )). In the case that all adhesions
i

30

b of V (G) for which there are
b λ to be the set of labelings λ
are diﬀerent, we deﬁne Λ
′
′
′
′
ρ1 ∈ τ1 Θ1 , . . . , ρℓ ∈ τℓ Θℓ such that
b β(t) = λ,
1. λ|
b

b

b

b

2. viλ < vjλ , if vi ∈ Zi , vj ∈ Zj and Siλ ≺ Sjλ (the ordering ≺ of subsets of N as
deﬁned in the preliminaries) and,

3. v λ < uλ , if v, u ∈ Zi and v ρi < uρi .
b

b

In the case that all adhesion sets are equal, we replace (2) by: viλ < vjλ , if vi ∈ Zi , vj ∈
b

Zj and λ−1 τi Θi ≺χ λ−1 τj Θj . The former case implicitly implies Ziλ = Z ρi + m for
some ρi ∈ τi′ Θ′i and some integer m. However, in the latter case we additionally state
this as an explicit condition.
b as the smallest coset containing S
b
b
We deﬁne Λ
λ∈Λ Λλ . Let µ ∈ Λ. We deﬁne a
µ
κ
κ
µ
map κ : S → {1, . . . , |S|} such that v < u , if and only if v < uµ . This is an
isomorphism-invariant renaming of the vertices such that S µκ = {1, . . . , |S|}. Return
b
Λκ.

(Canonical labeling.) Property (CL1) is clearly satisﬁed. We claim that for a partially cosetlabeled decomposition (T, β, α) the output of the algorithm is a non-empty coset A(I) that
satisﬁes (CL2) and (CL3). The correctness of the ﬁrst case is easy to see. The returned
set is non-empty because every graph of tree width at most k is k-degenerate and therefore
each subgraph has a vertex of degree at most k.
We consider the second case.
(CL2) We consider the result of applying the algorithm to Gτ for any τ ∈ Label(V (G)).
So the initial input of the algorithm is (T, β)τ instead of (T, β). Let τ |i := τ |V (Gi ) . The
children of the root of T τ has the decompositions (Ti , βi , αi )τ |i with the corresponding
τ|
graphs Gi i instead. By induction we assume that (CL2) holds for subgraphs of G. Property
(CL2) implies that even for an arbitrary bijection τ |i (which image is not necessary a
τ|
τ|
start segment of N) it holds that (τi Θi )τ |i = A(Gi i , Si i , (Ti , βi , α)τ |i ). Let τ |0 := τ |β(t) .
We get α(t)τ |0 instead of α(t) and get (ψ∆)τ |0 instead of ψ∆. Exemplarily we explain
the case when all adhesion sets are diﬀerent. In this case we get τ |−1
0 Λ instead of Λ.
−1
Since λ−1 ρi = (τ |0−1 λ)−1 τ |−1
ρ
we
chose
τ
|
ρ
as
a
minimal
element
instead of ρi and
i
i
i
i
−1 ′ ′
′
′
this leads to τ |i τi Θi instead of τi Θi . Because of (CL2) of the canonical labelings of a
b
b
λ
τ τ −1 λ
hypergraph with coset-labeled hyperedges we get τ |−1
0 Λ instead of Λ. Since v = v
S
b λ and ﬁnally τ −1
b
for all v ∈ G, we get τ −1 Λ
λ∈Λ Λλ . Observe that the smallest coset
S
−1
−1
b
b
containing τ
Λ which shows the correctness.
λ∈Λ Λλ is actually τ
(CL3) The ﬁrst inclusion Aut(G, S, (T, β, α))π S
⊆ A(I) follows from (CL2). It remains
′
b
b
b β(t) = λ and λ
b′ |β(t) = λ′ .
b λ and λ|
to prove A(I) ⊆ Aut(G)π. Assume we have λ, λ ∈ λ∈Λ Λ
bλ
b′−1 is an automorphism of G. Since both λ, λ′ ∈ Λ ≤ CL(G[β(t)]; α(t))
We have to show λ
31

we conclude that λλ′−1 preserves the edge relation E(β(t)). With the same argument λλ′−1
preserves S. Exemplarily, we explain the case when all adhesion sets are diﬀerent. We have
b
b′
I λ = I λ and therefore λλ′−1 preserves {Si }, {τi Θi |Si } and χ. So assume that λλ′−1 maps
bλ
b′−1 is an isomorphism from Gi to Gj . By construction
Si to Sj . It remains to show that λ
b Z = ρi + m and λ
b′ |Z = ρ′ + m′ for ρi ∈ τ ′ Θ′ , ρj ∈ τ ′ Θ′ . In fact it must be
we have λ|
i
j
j
i i
j j
′
′
′
b
b
the case that m = m , because the labeling of λ, λ is ordered according to the Siλ = Sjλ
b Z (λ
b′ |Z )−1 = ρi |Z (ρ′ |Z )−1 . Since
as required in (2). Since m = m′ we conclude λ|
i

j

i

j

j

λλ′−1 preserves {τi Θi |Si } we conclude λ−1 τi Θi |Si = λ′−1 τj Θj |Sj and we get λ−1 ρi |Si =
b S (λ
b′ |S )−1 =
λ′−1 ρj |Sj by the minimality of the elements in τi′ Θ′i and τj′ Θ′j . This gives us λ|
i
j
b Z (λ
b′ |Z )−1 = ρi |Z (ρ′ |Z )−1
λ|Si (λ′ |Sj )−1 = ρi |Si (ρ′j |Sj )−1 . We already noticed that λ|
i
j
i
j j
′
−1
′
−1
b
b
which leads to λ|V (λ |V )
= ρi |V (ρ |V ) . Since χ is preserved, we know that that
i

Gρi i

=

ρ
Gj j

j

and therefore

i

bb′−1
Giλλ

j

j

bλ
b′−1 is an isomorphism.
= Gj which means that λ

(Running time.) Due to dynamic programming the number of calls is polynomial in
|V (G)|. More precisely, for each bag of the clique separator decomposition, we construct
a coset-labeled tree decomposition and both have polynomial many bags. In the ﬁrst
case the construction of the coset-labeled tree decomposition from Theorem 9 takes time
2
2O(k log k) |V (G)|O(1) . Consider the Case “β(t) is labeled” in which all adhesion sets are
diﬀerent. By Property (L1) of the bag size of β(t) is bounded by cL and by Property
(L2) the number of children is bounded by kc2L + 2k cL . By Property (L2) we know that
cw(α(t)) ≤ k+1 and also cw(τi Θi |Si ) ≤ k+1 since τi Θi |Si is a subcoset of α(ti )κ. Therefore
the canonization algorithm for the hypergraph with coset-labeled hyperedges in Lemma 23
2
O(max{cw(α(t)),cw(α(ti ))})
runs in time (cL (kc2L + 2k cL ))
⊆ 2O(k log k) . Next, consider the second case in which all adhesion sets are equal. In this case, we have that the bag size of β(t)
is bounded by cM due to Property (L3) of our coset-labeled tree decomposition from Theorem 9. Therefore the canonization algorithm for the multiple colored cosets in Lemma 24
2
runs in time cM !|V (G)|O(1) ⊆ 2O(k log k) |V (G)|O(1) .

References
[Bab16]

László Babai. Graph isomorphism in quasipolynomial time [extended abstract].
In Daniel Wichs and Yishay 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.

[BKL83] László Babai, William M. Kantor, and Eugene M. Luks. Computational complexity and the classiﬁcation of ﬁnite simple groups. In 24th Annual Symposium
on Foundations of Computer Science, Tucson, Arizona, USA, 7-9 November
1983, pages 162–171. IEEE Computer Society, 1983.

32

[BL83]

László Babai and Eugene M Luks. Canonical labeling of graphs. In Proceedings
of the fifteenth annual ACM symposium on Theory of computing, pages 171–183.
ACM, 1983.

[Bod90]

Hans L. Bodlaender. Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees. J. Algorithms, 11(4):631–643, 1990.

[ES16]

Michael Elberfeld and Pascal Schweitzer. Canonizing graphs of bounded tree
width in logspace. In STACS, volume 47 of LIPIcs, pages 32:1–32:14. Schloss
Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016.

[GM15]

M. Grohe and D. Marx. Structure theorem and isomorphism test for graphs
with excluded topological subgraphs. sicomp, 44(1):114–159, 2015.

[GNS18] Martin Grohe, Daniel Neuen, and Pascal Schweitzer. Towards faster isomorphism tests for bounded degree graphs. CoRR, abs/1802.04659, 2018.
[GS15]

Martin Grohe and Pascal Schweitzer. Isomorphism testing for graphs of bounded
rank width. In Venkatesan Guruswami, editor, IEEE 56th Annual Symposium
on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20
October, 2015, pages 1010–1029. IEEE Computer Society, 2015.

[Lei93]

Hanns-Georg Leimer. Optimal decomposition by clique separators. Discrete
Mathematics, 113(1-3):99–123, 1993.

[LPPS17] Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh.
Fixed-parameter tractable canonization and isomorphism test for graphs of
bounded treewidth. SIAM Journal on Computing, 46(1):161–189, 2017.
[LS99]

Martin Liebeck and Aner Shalev. Simple groups, permutation groups, and probability. Journal of the American Mathematical Society, 12(2):497–520, 1999.

[Luk82]

Eugene M Luks. Isomorphism of graphs of bounded valence can be tested in
polynomial time. Journal of computer and system sciences, 25(1):42–65, 1982.

[Mat79]

Rudolf Mathon. A note on the graph isomorphism counting problem. Inf.
Process. Lett., 8(3):131–132, 1979.

[Mil83]

Gary Miller. Isomorphism testing and canonical forms for k-contractable graphs
(a generalization of bounded valence and bounded genus). In Foundations of
Computation Theory, pages 310–327. Springer, 1983.

[Neu16]

Daniel Neuen. Graph isomorphism for unit square graphs. In Piotr Sankowski
and Christos D. Zaroliagis, editors, 24th Annual European Symposium on Algorithms, ESA 2016, August 22-24, 2016, Aarhus, Denmark, volume 57 of LIPIcs,
pages 70:1–70:17. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016.
33

[OS14]

Yota Otachi and Pascal Schweitzer. Reduction techniques for graph isomorphism
in the context of width parameters. In SWAT, volume 8503 of Lecture Notes in
Computer Science, pages 368–379. Springer, 2014.

[Pon91]

Ilia N. Ponomarenko. The isomorphism problem for classes of graphs closed
under contraction. Journal of Mathematical Sciences, 55(2):1621–1643, 1991.

34

