Theorem 1.1.
There exists an algorithm that given a graph
H
and an
H
-minor-free graph
G
,
works in time f(H)·nO(1) for some function fand outputs a canonical labeling of G.
Here, a canonical labeling of
G
is a labeling of the vertices of
G
with labels from [
|V
(
G
)
|
] =
{
1
,...,|V
(
G
)
|}
so that for any two isomorphic graphs
G
and
G0
, the mapping matching vertices
with equal labels in
G
and
G0
is an isomorphism between
G
and
G0
. Thus, our algorithm solves the
more general Canonization problems, while Graph Isomorphism can be solved by computing
the canonical labelings for both input graphs and comparing the obtained labeled graphs.
The caveat in Theorem 1.1 is that we are not able to guarantee that
f
is computable. This
makes the algorithm formally fall outside of the usual definitions of fixed-parameter tractability (see
e.g. [
CFK+15
]), but we still allow ourselves to call it an FPT algorithm for Graph Isomorphism
and Canonization parameterized by the size of an excluded minor. We stress that we obtain a
single algorithm that takes Hon input, and not a different algorithm for every fixed H.
We now describe the ideas standing behind the proof of Theorem 1.1. First, we need to take
a closer look at the FPT algorithm for Graph Isomorphism and Canonization for graphs of
bounded treewidth [
LPPS17
,
GNSW20
]. There, the goal is to obtain an isomorphism-invariant tree
decomposition of the input graph of width bounded in parameter; then, to test isomorphism of two
graphs it suffices to test isomorphism of such decompositions. Unfortunately, it is actually impossible
to find one such isomorphism-invariant tree decomposition of the input graph; for instance, in a
long cycle one needs to arbitrarily break symmetry at some moment. However, up to technical
details, it suffices and is possible to find a small isomorphism-invariant family of tree decompositions.
To achieve this goal, the algorithm of [
LPPS17
] heavily relies on the existing understanding of
parameterized algorithms for approximating the treewidth of a graph.
The initial idea behind our approach is to borrow more tools from the literature on parameterized
graph separation problems, in particular from the work on the technique of recursive understand-
ing [
KT11
,
CCH+16
,
CLP+19
,
CKL+21
]. This work culminated in the following decomposition
theorem for graphs, proved by a superset of authors.
Theorem 1.2
([
CKL+21
])
.
Given a graph
G
and an integer
k
, one can in time 2
O(klog k)nO(1)
compute a tree decomposition of
G
where every adhesion is of size at most
k
and for every bag
S
the following holds: for every separation (
A, B
)in
G
of order at most
k
, either
|A∩S|6|A∩B|
or |B∩S|6|A∩B|.
The last property of Theorem 1.2 says that a bag
S
of the tree decomposition cannot be broken
by a separation of order at most
k
into two parts that both contain a large portion of
S
. This
property is often called unbreakability. More formally, let us recall the notion of a (
q, k
)-unbreakable
set introduced in [
CCH+16
,
CLP+19
]. Given a graph
G
and integers
q>k>
0, we say that a
set
S⊆V
(
G
) is (
q, k
)-unbreakable if for every separation (
A, B
) in
G
of order at most
k
, we have
|A∩S|6q
or
|B∩S|6q
. Theorem 1.2 of [
CKL+21
] can be seen as a simpler and cleaner version
of an analogous result of [
CLP+19
], where the bags are only guaranteed to be (
q, k
)-unbreakable
for some
q
bounded exponentially in
k
, and adhesion sizes are also bounded only exponentially in
k
.
Theorem 1.2 and its predecessor from [
CLP+19
] have been used to design parameterized
algorithms for several graph separation problems [CLP+19,CKL+21], most notably for Minimum
Bisection. In most cases, when looking for a deletion set of size at most
k
, one performs dynamic
programming on the tree decomposition provided by Theorem 1.2, where every step handling a single
bag can be solved using color-coding thanks to the unbreakability of the bag. More recent applications
include a parameterized approximation scheme for Min k-Cut [LSS20], as well as algorithms and
data structures for problems definable in first-order logic with connectivity predicates [PSS+21].
In this paper we propose to use the ideas behind the tree decomposition of Theorem 1.2 in the
context of Graph Isomorphism and Canonization in order to provide a reduction to the case
2