disposition vertex/.style=draw,circle,fill=gray, every
node/.style=anchor=center, lbl/.style=color=lightgray

# An Algorithmic Meta Theorem for Homomorphism Indistinguishability

Tim Seppelt
RWTH Aachen University
<EMAIL_ADDRESS>0000-0002-6447-0568

###### Abstract

Two graphs $G$ and $H$ are _homomorphism indistinguishable_ over a family of
graphs $\mathcal{F}$ if for all graphs $F\in\mathcal{F}$ the number of
homomorphisms from $F$ to $G$ is equal to the number of homomorphism from $F$
to $H$. Many natural equivalence relations comparing graphs such as (quantum)
isomorphism, cospectrality, and logical equivalences can be characterised as
homomorphism indistinguishability relations over various graph classes.

For a fixed graph class $\mathcal{F}$, the decision problem
HomInd($\mathcal{F}$) asks to determine whether two input graphs $G$ and $H$
are homomorphism indistinguishable over $\mathcal{F}$. The problem
HomInd($\mathcal{F}$) is known to be decidable only for few graph classes
$\mathcal{F}$. We show that HomInd($\mathcal{F}$) admits a randomised
polynomial-time algorithm for every graph class $\mathcal{F}$ of bounded
treewidth which is definable in counting monadic second-order logic
$\mathsf{CMSO}_{2}$. Thereby, we give the first general algorithm for deciding
homomorphism indistinguishability.

This result extends to a version of HomInd where the graph class $\mathcal{F}$
is specified by a $\mathsf{CMSO}_{2}$-sentence and a bound $k$ on the
treewidth, which are given as input. For fixed $k$, this problem is randomised
fixed-parameter tractable. If $k$ is part of the input then it is coNP- and
coW[1]-hard. Addressing a problem posed by Berkholz (2012), we show coNP-
hardness by establishing that deciding indistinguishability under the
$k$-dimensional Weisfeiler–Leman algorithm is coNP-hard when $k$ is part of
the input.

##  1 Introduction

In 1967, Lovász [30] proved that two graphs $G$ and $H$ are isomorphic if and
only if they are _homomorphism indistinguishable_ over all graphs, i.e. they
admit the same number of homomorphisms from every graph $F$. Subsequently,
many graph isomorphism relaxations have been characterised as homomorphism
indistinguishability relations. For example, two graphs are quantum isomorphic
if and only if they are homomorphism indistinguishable over all planar graphs
[32]. Moreover, two graphs satisfy the same sentences in $k$-variable first-
order logic with counting quantifiers if and only if they are homomorphism
indistinguishable over all graphs of treewidth less than $k$ [20, 19]. A
substantial list of similar results characterises notions from quantum
information [32, 6], finite model theory [20, 23, 21], convex optimisation
[19, 27, 37], algebraic graph theory [19, 27], machine learning [33, 40, 24],
and category theory [18, 2] as homomorphism indistinguishability relations.

The wealth of such examples motivates a more principled study of homomorphism
indistinguishability [4, 36, 39]. From a computational perspective, the
central question on homomorphism indistinguishability concerns the complexity
and computability of the following decision problem [36, Question 9]:

HomInd($\mathcal{F}$) Input: Graphs $G$ and $H$. Question: Are $G$ and $H$
homomorphism indistinguishable over $\mathcal{F}$?

Here, we consider the graph class $\mathcal{F}$ to be fixed and not part of
the input. The graphs $G$ and $H$ may be arbitrary graphs and do not necessary
have to be in $\mathcal{F}$. Typically, the graph class $\mathcal{F}$ is
infinite. Thus, the trivial approach to HomInd($\mathcal{F}$) of checking
whether $G$ and $H$ have the same number of homomorphisms from every
$F\in\mathcal{F}$ does not even render HomInd($\mathcal{F}$) decidable.

In general, the understanding of HomInd($\mathcal{F}$) is limited and does not
go beyond a short list of examples. For arguably artificial graph classes
$\mathcal{F}$, HomInd($\mathcal{F}$) can be arbitrarily hard [13, 39].
However, even for natural graph classes $\mathcal{F}$ the complexity-theoretic
landscape of HomInd($\mathcal{F}$) is diverse:

For the class $\mathcal{G}$ of all graphs, HomInd($\mathcal{G}$) is graph
isomorphism [30], a problem representing a long standing complexity-theoretic
challenge and currently only known to be in quasi-polynomial time [7]. For the
class $\mathcal{P}$ of all planar graphs, HomInd($\mathcal{P}$) is undecidable
[32]. For the class $\mathcal{K}$ of all cliques, HomInd($\mathcal{K}$) is
decidable, yet $\mathsf{C}_{=}\mathsf{P}$-hard [13]. Finally, for the class
$\mathcal{TW}_{k}$ of all graphs of treewidth at most $k$,
HomInd($\mathcal{TW}_{k}$) can be solved in polynomial time using the well-
known $k$-dimensional Weisfeiler–Leman algorithm [20, 14].

In this work, we generalise the last example by establishing that
HomInd($\mathcal{F}$) is tractable for every recognisable graph class
$\mathcal{F}$ of bounded treewidth thus giving the first general algorithm for
deciding homomorphism indistinguishability.

######  Theorem 1.1 (restate=mainRP, label=).

Let $k\geq 1$. If $\mathcal{F}$ is a $k$-recognisable graph class of treewidth
at most $k-1$ then HomInd($\mathcal{F}$) is in coRP.

Spelled out, Theorem 1.1 asserts that there exists a randomised algorithm for
HomInd($\mathcal{F}$) which always runs in polynomial time, accepts all YES-
instances and incorrectly accepts NO-instances with probability less than one
half. Recognisability is a notion arising in the context of Courcelle’s
theorem [15] on model checking, cf. Definition 2.10. Courcelle showed that
every graph class definable in counting monadic second-order logic
$\mathsf{CMSO}_{2}$ is recognisable. This subsumes graph classes defined by
forbidden (induced) subgraphs and minors, and by the Robertson–Seymour
Theorem, all minor-closed graph classes.

Thereby, Theorem 1.1 applies to e.g. the class of graphs of bounded
branchwidth, $k$-outerplanar graphs, and the class of trees of bounded degree.
The theorem also applies to the graph classes arising in homomorphism
indistinguishability characterisations for the Lasserre semidefinite
programming hierarchy [37]. In this way, we answer a question raised in [37]
affirmatively, cf. Theorem 8.1.

The proof of Theorem 1.1 combines Courcelle’s graph algebras [16] with the
homomorphism tensors from [32, 27]. Graph algebras comprise labelled graphs
and operations on them such as series and parallel composition. Homomorphism
tensors keep track of homomorphism counts of labelled graphs. We show that
recognisability and bounded treewidth guarantee that homomorphism tensors
yield finite-dimensional representations of suitable graph algebras which
certify homomorphism indistinguishability and are efficiently computable.

Observing that the dimension of the space of homomorphism tensors corresponds
to the number of labels of the labelled graphs in the graph algebra which they
represent, one might conjecture the following: The problem
HomInd($\mathcal{F}$) should be decidable if and only if the graph class
$\mathcal{F}$ can be generated as family of labelled graphs with a bounded
number of labels, cf. 10.1. Indeed, for planar graphs $\mathcal{P}$, the
result [32] of Mančinska and Roberson requires an unbounded number of labels
and characterises homomorphism indistinguishability over $\mathcal{P}$ as the
existence of some infinite-dimensional operator. Intuitively,
HomInd($\mathcal{P}$) is undecidable as it requires solving an infinite-
dimensional system of equations. Our Theorem 1.1 makes the other direction of
this vague argument precise: We show that if the number of labels is bounded
(e.g. the graph class has bounded treewidth) then considering finite-
dimensional spaces suffices, rendering the problem tractable.

Theorem 1.1 can be strengthened in several ways. Firstly, the connection to
Courcelle’s theorem motivates considering the following parametrised problem:

HomInd
Input: Graphs $G$, $H$, a $\mathsf{CMSO}_{2}$-sentence $\varphi$, an integer
$k$. Parameter: $|\varphi|+k$. Question: Are $G$ and $H$ homomorphism
indistinguishable over $\mathcal{F}_{\varphi,k}\coloneqq\\{\text{graph }F\mid
F\models\varphi\text{ and }\operatorname{tw}F\leq k-1\\}$?

The logical sentence $\varphi$ allows the graph class to be specified as part
of the input. We generalise Theorem 1.1 as follows:

######  Theorem 1.2 (restate=mainFPT, label=).

There exists a computable function $f\colon\mathbb{N}\to\mathbb{N}$ and a
randomised algorithm for HomInd of runtime $f(|\varphi|+k)n^{O(k)}$ for
$n\coloneqq\max\\{|V(G)|,|V(H)|\\}$ which accepts all YES-instances and
accepts NO-instances with probability less than one half.

While Theorem 1.1 does not depend on Courcelle’s work beyond the notion of
recognisability, Theorem 1.2 uses his result asserting that given a
$\mathsf{CMSO}_{2}$-sentence $\varphi$ and $k\in\mathbb{N}$ a finite automaton
can be computed which accepts width-$k$ tree-decomposed graphs satisfying
$\varphi$. Based on this automaton, our algorithm for Theorem 1.2 computes a
basis for finite-dimensional vector spaces of homomorphism tensors associated
to each of its states.

Theorem 1.1 is significant in light of the fact that HomInd($\mathcal{F}$) was
previously not even known to be decidable for most graph classes $\mathcal{F}$
in its scope. Despite that, it would be desirable to eliminate the need for
randomness. We accomplish this for a large range of graph classes:

######  Theorem 1.3 (restate=mainPW, label=).

Let $k\geq 1$. If $\mathcal{F}$ is a $k$-recognisable graph class of pathwidth
at most $k-1$ then HomInd($\mathcal{F}$) is in polynomial time.

Furthermore, we show similarly to Theorem 1.2 that the analogue of HomInd with
pathwidth instead of treewidth admits a deterministic algorithm of runtime
$f(|\varphi|+k)n^{O(k)}$, cf. Theorem 7.2.

Equipped with the parametrised perspective offered by HomInd, we finally
consider lower bounds on the complexity of this problem. Firstly, we show that
it is coW[1]-hard and that the runtime of the algorithm that yielded Theorem
1.3 is optimal under the Exponential Time Hypothesis (ETH).

######  Theorem 1.4 (restate=mainD, label=).

HomInd is coW[1]-hard under fpt-reductions. Unless ETH fails, there is no
algorithm for HomInd that runs in time $f(|\varphi|+k)n^{o(|\varphi|+k)}$ for
any computable function $f\colon\mathbb{N}\to\mathbb{N}$.

Secondly, we show that, when disregarding the parametrisation, HomInd is coNP-
hard. We do so by showing coNP-hardness of the following problem involving the
Weisfeiler–Leman (WL) algorithm. Theorem 1.5 is a first step towards resolving
a problem posed by Berkholz [8]: Is the decision problem in Theorem 1.5
EXPTIME-complete?

######  Theorem 1.5 (restate=mainC, label=).

The problem of deciding given graphs $G$ and $H$ and an integer
$k\in\mathbb{N}$ whether $G$ and $H$ are $k$-WL indistinguishable is coNP-hard
under polynomial-time many-one reductions.

WL is an important heuristic in graph isomorphism and tightly related to
notions in finite model theory [14] and graph neural networks [40, 33, 24].
The best known algorithm for WL runs in time $O(k^{2}n^{k+1}\log n)$ [28],
which is exponential when regarding $k$ as part of the input. It was shown
that when $k$ is fixed then the problem is PTIME-complete [22]. Establishing
lower bounds on the complexity of WL is a challenging problem [8, 9, 25].

##  2 Preliminaries

All graphs in this work are simple, undirected, and without multiple edges.
For a graph $G$, we write $V(G)$ for its vertex set and $E(G)$ for its edge
set. A _homomorphism_ $h\colon F\to G$ from a graph $F$ to a graph $G$ is a
map $V(F)\to V(G)$ such that $h(u)h(v)\in E(G)$ for all $uv\in E(F)$. Write
$\hom(F,G)$ from the number of homomorphisms from $F$ to $G$.

Two graph $G$ and $H$ are _homomorphism indistinguishable_ over a class of
graph $\mathcal{F}$, in symbols $G\equiv_{\mathcal{F}}H$, if
$\hom(F,G)=\hom(F,H)$ for all $F\in\mathcal{F}$. For an integer $n\geq 2$, $G$
and $H$ are _homomorphism indistinguishable over $\mathcal{F}$ modulo $n$_, in
symbols $G\equiv_{\mathcal{F}}^{n}H$, if $\hom(F,G)\equiv\hom(F,H)\mod n$ for
all $F\in\mathcal{F}$, cf. [29].

Let $\log$ denote the logarithm to base $2$. We recall the following
consequences of (an explicit version of) the Prime Number Theorem [38].

######  Fact 2.1.

For $n\geq e^{2000}$, the following hold:

  1. 1.

the number of primes $n<p\leq n^{2}$ is at least $\frac{n^{2}}{2\log n}$,

  2. 2.

the product of all primes $n<p\leq n^{2}$ is at least is $2^{n^{2}/2}$,

  3. 3.

the probability that a random number $n<m\leq n^{2}$ is prime is
$\geq\frac{1}{2\log n}$.

###### Proof.

Let $\ln$ denote the natural logarithm. Let $\pi(n)$ denote the number of
primes $\leq n$. By [38, Theorem 30A], for $n\geq e^{2000}$,

$\frac{n}{\ln n}<\pi(n)<\frac{n}{\ln n-2}.$

Thus the desired quantity $\pi(n^{2})-\pi(n)$ is at least

$\displaystyle\frac{n^{2}}{2\ln n}-\frac{n}{\ln n-2}\geq\frac{n^{2}}{2\ln
n}-\frac{2n}{\ln n}=\frac{n^{2}-4n}{2\ln n}\geq\frac{n^{2}\ln 2}{2\ln n}.$

For the second claim, the product of the primes is $>n^{\frac{n^{2}}{2\log
n}}=2^{\frac{n^{2}}{2\log n}\log n}=2^{n^{2}/2}$. For the third claim,
$\frac{n^{2}}{2\log n}\cdot\frac{1}{n^{2}-n}\geq\frac{1}{2\log n}$. ∎

###  2.1 (Bi)labelled Graphs and Homomorphism Tensors

Let $k,\ell\geq 1$. A _$k$ -labelled graph_ is a tuple
$\boldsymbol{F}=(F,\boldsymbol{u})$ where $F$ is a graph and
$\boldsymbol{u}\in V(F)^{k}$ is a $k$-tuple with distinct entries. We say
$u_{i}\in V(F)$, the $i$-th entry of $\boldsymbol{u}$, _carries the $i$-th
label_. Write $\mathcal{G}(k)$ for the class of $k$-labelled graphs. A
$k$-labelled graph $\boldsymbol{F}=(F,\boldsymbol{u})$ is _distinctly
$k$-labelled_ if $u_{i}\neq u_{j}$ for all $1\leq i<j\leq k$. Write
$\mathcal{D}(k)$ for the class of distinctly $k$-labelled graphs.

A _$(k,\ell)$ -bilabelled graph_ is a tuple
$\boldsymbol{F}=(F,\boldsymbol{u},\boldsymbol{v})$ where $F$ is a graph and
$\boldsymbol{u}\in V(F)^{k}$ and $\boldsymbol{v}\in V(F)^{\ell}$. It is
_distinctly $(k,\ell)$-bilabelled_ if $u_{i}\neq u_{j}$ for all $1\leq i<j\leq
k$ and $v_{i}\neq v_{j}$ for all $1\leq i<j\leq\ell$. Note that
$\boldsymbol{u}$ and $\boldsymbol{v}$ might share entries. We say $u_{i}\in
V(F)$ and $v_{i}\in V(F)$ _carry the $i$-th in-label_ and _out-label_ ,
respectively. Write $\mathcal{G}(k,\ell)$ for the class of
$(k,\ell)$-bilabelled graphs and $\mathcal{D}(k,\ell)$ for the class of
distinctly $(k,\ell)$-bilabelled graphs.

For a graph $G$, and $\boldsymbol{F}=(F,\boldsymbol{u})\in\mathcal{G}(k)$
define its _homomorphism tensor_ $\boldsymbol{F}_{G}\in\mathbb{N}^{V(G)^{k}}$
whose $\boldsymbol{v}$-th entry is equal to the number of homomorphisms
$h\colon F\to G$ such that $h(u_{i})=v_{i}$ for all $i\in[k]$. Analogously,
for $\boldsymbol{F}\in\mathcal{G}(k,\ell)$, define
$\boldsymbol{F}_{G}\in\mathbb{N}^{V(G)^{k}\times V(G)^{\ell}}$. As the entries
of homomorphism tensors are integral, we can view them as vectors in vector
spaces over $\mathbb{R}$ as in Section 3 or over finite fields
$\mathbb{F}_{p}$ as in Section 4.

As observed in [32, 27], cf. [37], (bi)labelled graphs and their homomorphism
tensors are intriguing due to the following correspondences between
combinatorial operations on the former and algebraic operations on the latter:

Dropping labels corresponds to sum-of-entries (soe): For
$\boldsymbol{F}=(F,\boldsymbol{u})\in\mathcal{G}(k)$, define
$\operatorname{soe}\boldsymbol{F}\coloneqq F$ as the underlying unlabelled
graph of $\boldsymbol{F}$. Then for all graphs $G$,
$\hom(\operatorname{soe}\boldsymbol{F},G)=\sum_{\boldsymbol{v}\in
V(G)^{k}}\boldsymbol{F}_{G}(\boldsymbol{v})\eqqcolon\operatorname{soe}(\boldsymbol{F}_{G})$.

Gluing corresponds to Schur products: For $\boldsymbol{F}=(F,\boldsymbol{u})$
and $\boldsymbol{F}^{\prime}=(F^{\prime},\boldsymbol{u}^{\prime})$ in
$\mathcal{G}(k)$, define
$\boldsymbol{F}\odot\boldsymbol{F}^{\prime}\in\mathcal{G}(k)$ as the
distinctly $k$-labelled graph obtained by taking the disjoint union of $F$ and
$F^{\prime}$ and placing the $i$-th label at the vertex obtained by merging
$u_{i}$ with $u^{\prime}_{i}$ for all $i\in[k]$. Then for every graph $G$ and
$\boldsymbol{v}\in V(G)^{k}$,
$(\boldsymbol{F}\odot\boldsymbol{F}^{\prime})_{G}(\boldsymbol{v})=\boldsymbol{F}_{G}(\boldsymbol{v})\boldsymbol{F}^{\prime}_{G}(\boldsymbol{v})\eqqcolon(\boldsymbol{F}_{G}\odot\boldsymbol{F}^{\prime}_{G})(\boldsymbol{v})$.
One may similarly define the gluing product of two $(k,\ell)$-bilabelled
graphs.

Series composition corresponds to matrix products: For
$\boldsymbol{K}=(K,\boldsymbol{u},\boldsymbol{v})$ and
$\boldsymbol{K}^{\prime}=(K^{\prime},\boldsymbol{u}^{\prime},\boldsymbol{v}^{\prime})$
in $\mathcal{G}(k,k)$, define
$\boldsymbol{K}\cdot\boldsymbol{K}^{\prime}\in\mathcal{G}(k,k)$ as the
bilabelled graph obtained by taking the disjoint union of $K$ and
$K^{\prime}$, identifying $v_{i}$ with $u^{\prime}_{i}$ for $i\in[k]$, and
placing the $i$-th in-label (out-label) on $u_{i}$ (on $v^{\prime}_{i}$) for
$i\in[k]$. Then for all graphs $G$ and $\boldsymbol{x},\boldsymbol{z}\in
V(G)^{k}$,
$(\boldsymbol{K}\cdot\boldsymbol{K}^{\prime})_{G}(\boldsymbol{x},\boldsymbol{z})=\sum_{\boldsymbol{y}\in
V(G)^{k}}\boldsymbol{K}_{G}(\boldsymbol{x},\boldsymbol{y})\boldsymbol{K}^{\prime}_{G}(\boldsymbol{y},\boldsymbol{z})\eqqcolon(\boldsymbol{K}_{G}\cdot\boldsymbol{K}^{\prime}_{G})(\boldsymbol{x},\boldsymbol{z}).$
One may similarly compose a graph in $\mathcal{G}(k,k)$ with a graph in
$\mathcal{G}(k)$ obtaining one in $\mathcal{G}(k)$. This operation correspond
to the matrix-vector product.

Note that all operations above restrict from (bi)labelled graphs to distinctly
(bi)labelled graphs. For example, the series product of two distinctly
bilabelled graphs is distinctly bilabelled.

Permutation of labels corresponds to permutation of axes: Let
$\boldsymbol{F}=(F,\boldsymbol{u},\boldsymbol{v})\in\mathcal{G}(k,\ell)$ and
write $\mathfrak{S}_{k+\ell}$ for the symmetric group acting on $k+\ell$
letters. For $\sigma\in\mathfrak{S}_{k+\ell}$, write
$\boldsymbol{F}^{\sigma}\coloneqq(F,\boldsymbol{x},\boldsymbol{y})$ where
$\boldsymbol{x}_{i}\coloneqq(\boldsymbol{uv})_{\sigma(i)}$ and
$\boldsymbol{y}_{j-k}\coloneqq(\boldsymbol{uv})_{\sigma(j)}$ for all $1\leq
i\leq k<j\leq k+\ell$, i.e. $\boldsymbol{F}^{\sigma}$ is obtained from
$\boldsymbol{F}$ by permuting the labels according to $\sigma$. Then for all
graphs $G$, $\boldsymbol{F}^{\sigma}_{G}$ is obtained from
$\boldsymbol{F}_{G}$ by permuting the axes of the tensor according to
$\sigma$, cf. [37].

###  2.2 Labelled Graphs of Bounded Treewidth

Labelled graphs of bounded treewidth represent the technical foundation of
most proofs in this article. Several versions of such have been discussed in
previous works [27, 16, 21].

Let $F$ be a graph. A _tree decomposition_ of $F$ is a pair $(T,\beta)$ where
$T$ is a tree and $\beta\colon V(T)\to 2^{V(F)}$ is a map such that

  1. 1.

the union of the $\beta(t)$ for $t\in V(T)$ is equal to $V(F)$,

  2. 2.

for every edge $e\in E(F)$ there exists $t\in V(T)$ such that
$e\subseteq\beta(t)$,

  3. 3.

for every vertex $u\in V(F)$ the set of vertices $t\in V(T)$ such that
$u\in\beta(t)$ is connected in $T$.

The _width_ of $(T,\beta)$ is the maximum over all $\lvert\beta(t)\rvert-1$
for $t\in V(T)$. The _treewidth_ $\operatorname{tw}F$ of $F$ is the minimum
width of a tree decomposition of $F$. A _path decomposition_ is a tree
decomposition $(T,\beta)$ where $T$ is a path. The _pathwidth_
$\operatorname{pw}F$ of $F$ is the minimum width of a path decomposition of
$F$.

The following Lemmas 2.2 and 2.3 introduce tree and path decompositions with
certain enjoyable properties.

######  Lemma 2.2 ([10, Lemma 8]).

Let $k\geq 1$ and $F$ be a graph such that $|V(F)|\geq k$. If
$\operatorname{tw}F\leq k-1$ then $F$ admits a tree decomposition $(T,\beta)$
such that

  1. 1.

$|\beta(t)|=k$ for all $t\in V(T)$,

  2. 2.

$|\beta(s)\cap\beta(t)|=k-1$ for all $st\in E(T)$.

If $\operatorname{pw}F\leq k-1$ then $F$ admits a path decomposition
$(T,\beta)$ satisfying Items 1 and 2.

The tree decompositions in Lemma 2.2 can be rearranged in order for the depth
of the decomposition tree to give a bound on the number of vertices in the
decomposed graph.

######  Lemma 2.3.

Let $k\geq 1$ and $F$ be a graph such that $\operatorname{tw}F\leq k-1$ and
$|V(F)|\geq k$. Then $F$ admits tree decomposition $(T,\beta)$ such that

  1. 1.

$|\beta(t)|=k$ for all $t\in V(T)$,

  2. 2.

$|\beta(s)\cap\beta(t)|=k-1$ for all $st\in E(T)$,

  3. 3.

there exists a vertex $r\in V(T)$ such that the out-degree of every vertex in
the rooted tree $(T,r)$ is at most $k$.

###### Proof.

Let $(T,\beta)$ be a tree decomposition satisfying the assertions of Lemma
2.2. Pick a root $r\in V(T)$ arbitrarily. To ensure that the last property
holds, the tree decomposition is modified recursively as follows:

By merging vertices, it can be ensured that no two children of $r$ carry the
same bag, i.e. that there exist no two children $s_{1}\neq s_{2}$ of $r$ such
that $\beta(s_{1})=\beta(s_{2})$.

For every $v\in\beta(r)$, let $C(v)$ denote the set of all children $t$ of $r$
such that $\beta(r)\setminus\beta(t)=\\{v\\}$, i.e. $C(v)$ is the set of all
children of $r$ whose bags do not contain the vertex $v$. The collection
$C(v)$ for $v\in\beta(r)$ is a partition of the children of $r$ in at most $k$
parts.

Note that for two distinct children $t_{1}\neq t_{2}$ in the same part $C(v)$
it holds that $|\beta(t_{1})\cap\beta(t_{2})|=k-1$. Rewire the children of $r$
as follows: For every $v\in\beta(r)$ with $C(v)\neq\emptyset$, pick $t\in
C(v)$, make $t$ a child of $r$ and all other elements of $C(v)$ children of
$t$.

The vertex $r$ now has at most $k$ children and the new tree decomposition
still satisfies the assertions of Lemma 2.2. Proceed by processing the
children of $r$. ∎

Inspired by Lemma 2.2, we consider the following family of distinctly labelled
graphs. The _depth_ of a rooted tree $(T,r)$ is the maximal number of vertices
on any path from $r$ to a leaf.

######  Definition 2.4.

Let $k,d\geq 1$. Define $\mathcal{TW}_{d}(k)$ as the set of all
$\boldsymbol{F}=(F,\boldsymbol{u})\in\mathcal{D}(k)$ such that $F$ admits a
tree decomposition $(T,\beta)$ of width $\leq k-1$ satisfying the assertions
of Lemma 2.3 with some $r\in V(T)$ such that
$\beta(r)=\\{u_{1},\dots,u_{k}\\}$ and $(T,r)$ is of depth at most $d$. Let
$\mathcal{TW}(k)\coloneqq\bigcup_{d\geq 1}\mathcal{TW}_{d}(k)$.

Crucially, this definition permits the following bound on the size of the
graphs in $\mathcal{TW}_{d}(k)$ in terms of $d$ and $k$.

######  Lemma 2.5.

Let $k,d\geq 1$. Every $\boldsymbol{F}\in\mathcal{TW}_{d}(k)$ has at most
$\max\\{k^{d},d\\}$ vertices.

###### Proof.

Let $(T,\beta)$ and $r\in V(T)$ be as in Definition 2.4. If $k=1$, then every
vertex in $(T,r)$ has out-degree $1$ and $F$ at most $d$ vertices.

Suppose that $k\geq 2$. The proof is by induction on the depth $d$ of the
rooted tree $(T,r)$. If $d=1$, then $T$ contains only a single vertex and
$\boldsymbol{F}$ has at most $k$ vertices.

For the inductive step, let $\boldsymbol{F}$ be of depth $d$. If $r$ has only
a single neighbour $s$, then $S\coloneqq T-r$ is such that $(S,s)$ is of depth
$d-1$. By the inductive hypothesis, $\left\lvert\bigcup_{s\in
V(S)}\beta(s)\right\rvert\leq k^{d}$. Furthermore, $\left\lvert\bigcup_{t\in
V(T)}\beta(t)\setminus\bigcup_{s\in V(S)}\beta(s)\right\rvert=1$. Hence,
$\boldsymbol{F}$ has at most $k^{d-1}+1\leq k^{d}$ many vertices.

If $r$ has multiple neighbours, observe that due to Lemma 2.3 every vertex in
$\beta(r)$ is also in $\beta(s)$ for some neighbour $s$ of $r$. Hence, the
number of vertices in $\boldsymbol{F}$ is bounded by the number of vertices
covered by the subtrees of $T-r$ rooted in $s$. Thus, $\boldsymbol{F}$ has at
most $k^{d-1}\cdot k\leq k^{d}$ many vertices. ∎

Clearly, if $\boldsymbol{F}\in\mathcal{TW}(k)$ then
$\operatorname{tw}(\operatorname{soe}\boldsymbol{F})\leq k-1$. Conversely, by
Lemma 2.3, for every $F$ with $\operatorname{tw}F\leq k-1$ and $\lvert
V(F)\rvert\geq k$, there exists $\boldsymbol{u}\in V(F)^{k}$ such that
$(F,\boldsymbol{u})\in\mathcal{TW}(k)$. Thus the underlying unlabelled graphs
of the labelled graphs in $\mathcal{TW}(k)$ are exactly the graphs of
treewidth $\leq k-1$ on $\geq k$ vertices.

The family $\mathcal{TW}(k)$ is generated by certain small building blocks
under series composition and gluing as follows.

Let $\boldsymbol{1}\in\mathcal{TW}_{1}(k)$ be the distinctly $k$-labelled
graph on $k$ vertices without any edges. For $i\in[k]$, let
$\boldsymbol{J}^{i}=(J^{i},(1,\dots,k),\allowbreak(1,\dots,i-1,\widehat{i},i+1,\dots,k))$
the distinctly $(k,k)$-bilabelled graph with
$V(J^{i})\coloneqq[k]\cup\\{\widehat{i}\\}$ and $E(J^{i})\coloneqq\emptyset$.
Writing $\binom{[k]}{2}$ for the set of pairs of distinct elements in $[k]$,
let $\boldsymbol{A}^{ij}=(A^{ij},(1,\dots,k),(1,\dots,k))$ for
$ij\in\binom{[k]}{2}$ be the distinctly $(k,k)$-bilabelled graph with
$V(A^{ij})\coloneqq[k]$ and $E(A^{ij})\coloneqq\\{ij\\}$. These graphs are
depicted in Figure 1. Let $\mathcal{B}(k)\coloneqq\\{\boldsymbol{J}^{i}\mid
i\in[k]\\}\allowbreak\cup\\{\boldsymbol{A}^{ij}\mid ij\in\binom{[k]}{2}\\}$.
Observe that $\lvert\mathcal{B}(k)\rvert\leq k^{2}$.

(a) [vertex] ; (ab) [vertex,below of=a] ; (b) [below of=ab, yshift=.5cm] ⋮;
(f) [below of=b,vertex, yshift=.3cm] ; (fb) [below of=f,vertex] ;

(a1) [lbl,left of=a] $1$; [color=lightgray] (a) – (a1);

(ab1) [lbl,left of=ab] $2$; [color=lightgray] (ab) – (ab1); (f1) [lbl,left
of=f] $k-1$; [color=lightgray] (f) – (f1); (fb1) [lbl,left of=fb] $k$;
[color=lightgray] (fb) – (fb1);

(a) $\boldsymbol{1}\in\mathcal{TW}(k)$.

(a) [vertex] ; (b) [below of=a, yshift=.5cm] ⋮; (c) [below of=b,vertex,
yshift=.3cm] ; (d) [below of=c,vertex] ; (e) [below of=d, yshift=.5cm] ⋮; (f)
[below of=e,vertex, yshift=.3cm] ; [ultra thick] (c) edge [bend left] (d); (e)
[below of=c, yshift=.6cm] ⋮;

(a1) [lbl,left of=a] $1$; (a2) [lbl,right of=a] $1$; [color=lightgray] (a) –
(a1); [color=lightgray] (a) – (a2);

(c1) [lbl,left of=c] $i$; (c2) [lbl,right of=c] $i$; [color=lightgray] (c) –
(c1); [color=lightgray] (c) – (c2); (d1) [lbl,left of=d] $j$; (d2) [lbl,right
of=d] $j$; [color=lightgray] (d) – (d1); [color=lightgray] (d) – (d2); (f1)
[lbl,left of=f] $k$; (f2) [lbl,right of=f] $k$; [color=lightgray] (f) – (f1);
[color=lightgray] (f) – (f2);

(b) $\boldsymbol{A}^{ij}\in\mathcal{D}(k,k)$.

(a) [vertex] ; (b) [below of=a, yshift=.5cm] ⋮; (c) [below of=b,vertex,
yshift=.3cm] ; (dx) [below of=c,vertex, xshift=-.5cm, yshift=.5cm] ; (dy)
[below of=c,vertex, xshift=.5cm, yshift=.5cm] ; (dz) [below of=dx,
xshift=.5cm,vertex, yshift=.5cm] ; (e) [below of=dz, yshift=.5cm] ⋮; (f)
[below of=e,vertex, yshift=.3cm] ;

(a1) [lbl,left of=a,xshift=-.5cm] $1$; (a2) [lbl,right of=a,xshift=.5cm] $1$;
[color=lightgray] (a) – (a1); [color=lightgray] (a) – (a2);

(c1) [lbl,left of=c,xshift=-.5cm] $i-1$; (c2) [lbl,right of=c,xshift=.5cm]
$i-1$; [color=lightgray] (c) – (c1); [color=lightgray] (c) – (c2); (d1)
[lbl,left of=dx] $i$; (d2) [lbl,right of=dy] $i$; [color=lightgray] (d1) to
(dx); [color=lightgray] (d2) to (dy);

(d3) [lbl,left of=dz,xshift=-.5cm] $i+1$; (d4) [lbl,right of=dz,xshift=.5cm]
$i+1$; [color=lightgray] (dz) – (d3); [color=lightgray] (dz) – (d4);

(f1) [lbl,left of=f,xshift=-.5cm] $k$; (f2) [lbl,right of=f,xshift=.5cm] $k$;
[color=lightgray] (f) – (f1); [color=lightgray] (f) – (f2);

(c) $\boldsymbol{J}^{i}\in\mathcal{D}(k,k)$.

Figure 1: The (bi)labelled generators of $\mathcal{TW}(k)$ in wire notion of
[32]. A vertex carries in-label (out-label) $i$ if it is connected to the
index $i$ on the left (right) by a wire. Actual edges and vertices of the
graph are depicted in black.

It can be readily verified that if $\boldsymbol{F}\in\mathcal{TW}(k)$ and
$\boldsymbol{B}\in\mathcal{B}(k)$ then
$\boldsymbol{B}\cdot\boldsymbol{F}\in\mathcal{TW}(k)$. Furthermore, if
$\boldsymbol{F},\boldsymbol{F}^{\prime}\in\mathcal{TW}(k)$ then
$\boldsymbol{F}\odot\boldsymbol{F}^{\prime}\in\mathcal{TW}(k)$. Conversely,
the elements of $\mathcal{B}(k)$ generate $\mathcal{TW}(k)$ in the following
sense:

######  Lemma 2.6.

Let $k\geq 1$. For every $\boldsymbol{F}\in\mathcal{TW}(k)$, one of the
following holds:

  1. 1.

$\boldsymbol{F}=\boldsymbol{1}$,

  2. 2.

$\boldsymbol{F}=\prod_{ij\in
A}\boldsymbol{A}^{ij}\cdot\boldsymbol{F}^{\prime}$ for some
$A\subseteq\binom{[k]}{2}$ and $\boldsymbol{F}^{\prime}\in\mathcal{TW}(k)$
with less edges than $\boldsymbol{F}$,

  3. 3.

$\boldsymbol{F}=\boldsymbol{J}^{i}\cdot\boldsymbol{F}^{\prime}$ for some
$i\in[k]$ and $\boldsymbol{F}^{\prime}\in\mathcal{TW}(k)$ with less vertices
than $\boldsymbol{F}$,

  4. 4.

$\boldsymbol{F}=\boldsymbol{F}_{1}\odot\boldsymbol{F}_{2}$ for
$\boldsymbol{F}_{1},\boldsymbol{F}_{2}\in\mathcal{TW}(k)$ on less vertices
than $\boldsymbol{F}$.

###### Proof.

Write $\boldsymbol{F}=(F,\boldsymbol{u})$ and let $(T,\beta)$ and $r\in V(T)$
be for $\boldsymbol{F}\in\mathcal{TW}(k)$ as in Definition 2.4.

For the second case, let $A=\\{ij\in\binom{[k]}{2}\mid u_{i}u_{j}\in E(F)\\}$.
Write $F^{\prime}$ for the graph obtained from $F$ by deleting the edges
$u_{i}u_{j}$ for $ij\in A$. Then
$\boldsymbol{F}^{\prime}\coloneqq(F^{\prime},\boldsymbol{u})\in\mathcal{TW}(k)$
and $\boldsymbol{F}=\prod_{ij\in
A}\boldsymbol{A}^{ij}\cdot\boldsymbol{F}^{\prime}$.

If $A=\emptyset$, distinguish two cases: The vertex $r$ has a unique neighbour
$s\in V(T)$. By the assertions of Lemma 2.2, there exists a unique $i\in[k]$
such that $u_{i}\not\in\beta(s)$. Let $F^{\prime}$ be the subgraph of $F$
induced by $\bigcup_{t\in V(T)\setminus\\{r\\}}\beta(t)$ and write
$\boldsymbol{v}\in V(F^{\prime})^{k}$ for the tuple of distinct vertices which
coincides with $\boldsymbol{u}$ everywhere except at the $i$-th entry where it
is equal to the unique vertex in $\beta(s)\setminus\beta(r)$. Then
$\boldsymbol{F}^{\prime}\coloneqq(F^{\prime},\boldsymbol{v})\in\mathcal{TW}(k)$
and $\boldsymbol{F}=\boldsymbol{J}^{i}\cdot\boldsymbol{F}^{\prime}$.

Finally, suppose that $r$ has multiple neighbours $s_{1},\dots,s_{m}\in V(T)$.
Let $T_{1}$ denote the connected component of $T-\\{s_{2},\dots,s_{m}\\}$
containing $s_{1}$. Let $T_{2}$ denote the connected component of
$T-\\{s_{1}\\}$ containing $s_{2},\dots,s_{m}$. For $j\in\\{1,2\\}$, let
$F_{j}$ be the subgraph induced by $\bigcup_{t\in V(T_{j})}\beta(t)$. Then
$F_{1}$ contains less vertices than $F$ since the vertex in
$\beta(s_{2})\setminus\beta(r)$ is not in $F_{1}$. Symmetrically, $F_{2}$
contains less vertices than $F$. Then
$\boldsymbol{F}_{j}\coloneqq(F_{j},\boldsymbol{u})\in\mathcal{TW}(k)$ for
$j\in\\{1,2\\}$. As desired,
$\boldsymbol{F}=\boldsymbol{F}_{1}\odot\boldsymbol{F}_{2}$. ∎

###  2.3 Labelled Graphs of Bounded Pathwidth

The set-up from Section 2.2 can be adapted for pathwidth as follows.

######  Definition 2.7.

For $k,d\geq 1$, write $\mathcal{PW}_{d}(k)\subseteq\mathcal{D}(k)$ for the
class of all distinctly $k$-labelled graphs
$\boldsymbol{F}=(F,\boldsymbol{u})$ such that there exists a path
decomposition $(P,\beta)$ of $F$ where

  1. 1.

$|\beta(t)|=k$ for all $t\in V(P)$,

  2. 2.

$|\beta(s)\cap\beta(t)|=k-1$ for all $st\in E(P)$,

  3. 3.

there exists a vertex $r\in V(P)$ of degree at most $1$ such that
$\beta(r)=\\{u_{1},\dots,u_{k}\\}$,

  4. 4.

$|V(P)|\leq d$.

Let $\mathcal{PW}(k)\coloneqq\bigcup_{d\geq 1}\mathcal{PW}_{d}(k)$.

By Lemma 2.2, for every graph $F$ with $\operatorname{pw}F\leq k-1$ on at
least $k$ vertices, there exists $\boldsymbol{u}\in V(F)^{k}$ such that
$(F,\boldsymbol{u})\in\mathcal{PW}(k)$. Conversely, the underlying graph of
every $\boldsymbol{F}\in\mathcal{PW}(k)$ has pathwidth at most $k-1$.
Analogously to Lemma 2.5, we obtain the following bound on the size of the
graphs in $\mathcal{PW}_{d}(k)$:

######  Lemma 2.8.

Let $k,d\geq 1$. Every $\boldsymbol{F}\in\mathcal{PW}_{d}(k)$ has at most
$k+d-1$ vertices.

###### Proof.

If $d=1$, then the path decomposition $(P,\beta)$ of $\boldsymbol{F}$ as in
Definition 2.7 has at most one bag and $\boldsymbol{F}$ has at most $k$
vertices. For larger $d$, observe that, when traversing the decomposition from
one end of $P$ to the other, every bag introduces exactly one new vertex.
Thus, there are at most $k+d-1$ vertices in $\boldsymbol{F}$. ∎

Similar to $\mathcal{TW}(k)$, $\mathcal{PW}(k)$ is generated by small building
blocks. For $\mathcal{PW}(k)$, only series composition needs to be considered.
Gluing is not permitted. Clearly, if $\boldsymbol{F}\in\mathcal{PW}(k)$ then
$\boldsymbol{B}\cdot\boldsymbol{F}\in\mathcal{PW}(k)$ for every
$\mathcal{B}(k)$.

######  Lemma 2.9.

Let $k\geq 1$. For every $\boldsymbol{F}\in\mathcal{PW}(k)$, one of the
following holds:

  1. 1.

$\boldsymbol{F}=\boldsymbol{1}$,

  2. 2.

$\boldsymbol{F}=\prod_{ij\in
A}\boldsymbol{A}^{ij}\cdot\boldsymbol{F}^{\prime}$ for some
$A\subseteq\binom{[k]}{2}$ and $\boldsymbol{F}^{\prime}\in\mathcal{PW}(k)$
with less edges than $\boldsymbol{F}$,

  3. 3.

$\boldsymbol{F}=\boldsymbol{J}^{i}\cdot\boldsymbol{F}^{\prime}$ for some
$i\in[k]$ and $\boldsymbol{F}^{\prime}\in\mathcal{PW}(k)$ with less vertices
than $\boldsymbol{F}$.

###### Proof.

Following the proof of Lemma 2.6, observe that the missing case does not
occur. ∎

###  2.4 Counting Monadic Second-Order Logic

We denote _first-order logic_ over the relational signature $\\{E\\}$ of
graphs by $\mathsf{FO}$. The logic $\mathsf{MSO}_{1}$ is the extension of
$\mathsf{FO}$ by variables $X,Y,Z,\dots$ which range over subsets of vertices
and atomic formulas $x\in X$. The logic $\mathsf{MSO}_{2}$ extends
$\mathsf{MSO}_{1}$ by first-order (monadic second-order) variables which range
over edges (sets of edges) and atomic formulas $\operatorname{inc}(x,y)$
evaluates to true if $x$ is assigned a vertex $v$ and $y$ is assigned an edge
$e$ such that $v$ is incident with $e$. _Counting monadic second-order logic_
$\mathsf{CMSO}_{2}$ is the extension of $\mathsf{MSO}_{2}$ by atomic formulas
$\operatorname{card}_{p,q}(X)$ for integers $p,q\in\mathbb{N}$ expressing
$\lvert X\rvert\equiv p\mod q$. See [16] for further details.

###  2.5 Recognisability

We consider the following definition of recognisability [12].

######  Definition 2.10.

Let $k\geq 1$. For class of unlabelled graphs $\mathcal{F}$, define the
equivalence relation $\sim_{\mathcal{F}}$ on the class of distinctly
$k$-labelled graphs $\mathcal{D}(k)$ by letting
$\boldsymbol{F}_{1}\sim_{\mathcal{F}}\boldsymbol{F}_{2}$ if and only if for
all $\boldsymbol{K}\in\mathcal{D}(k)$ it holds that

$\operatorname{soe}(\boldsymbol{K}\odot\boldsymbol{F}_{1})\in\mathcal{F}\iff\operatorname{soe}(\boldsymbol{K}\odot\boldsymbol{F}_{2})\in\mathcal{F}.$

The class $\mathcal{F}$ is _$k$ -recognisable_ if $\sim_{\mathcal{F}}$ has
finitely many equivalence classes. The number of classes is the _$k$
-recognisability index_ of $\mathcal{F}$.

To parse Definition 2.10, first recall that
$\boldsymbol{K}\odot\boldsymbol{F}_{1}$ is the $k$-labelled graph by gluing
$\boldsymbol{K}$ and $\boldsymbol{F}_{1}$ together at their labelled vertices.
The $\operatorname{soe}$-operator drops the labels yielding unlabelled graphs.
Intuitively, $\boldsymbol{F}_{1}\sim_{\mathcal{F}}\boldsymbol{F}_{2}$ iff both
or neither of their underlying unlabelled graphs are in $\mathcal{F}$ and the
positions of the labels in $\boldsymbol{F}_{1}$ and $\boldsymbol{F}_{2}$ is
equivalent with respect to membership in $\mathcal{F}$. Consider the following
example:

######  Example 2.11.

The class $\mathcal{W}$ of all paths is $1$-recognisable. Its
$1$-recognisability index is $4$. The equivalence classes are described by the
representatives in Figure 2.

[node distance=.7cm] (a) [vertex] ; (a1) [lbl,left of=a] $1$;
[color=lightgray] (a) – (a1);

(a) $\boldsymbol{1}$.

[node distance=.7cm] (a) [vertex] ; (b) [vertex, right of=a] ; [ultra thick]
(a) – (b); (a1) [lbl,left of=a] $1$; [color=lightgray] (a) – (a1);

(b) $\boldsymbol{P}$.

[node distance=.7cm] (a) [vertex] ; (b) [vertex, right of=a] ; (c) [vertex,
above of=a] ; [ultra thick] (a) – (b); [ultra thick] (a) – (c); (a1) [lbl,left
of=a] $1$; [color=lightgray] (a) – (a1);

(c) $\boldsymbol{Q}$.

[node distance=.7cm] (a) [vertex] ; (b) [vertex, right of=a] ; (c) [vertex,
above of=a] ; [ultra thick] (a) – (b); [ultra thick] (a) – (c); [ultra thick]
(b) – (c); (a1) [lbl,left of=a] $1$; [color=lightgray] (a) – (a1);

(d) $\boldsymbol{C}$.

Figure 2: Representatives for $\sim_{\mathcal{W}}$ for $k=1$ and $\mathcal{W}$
the class of paths from Example 2.11.

###### Proof.

To show that the labelled graphs in Figure 2 cover all equivalence classes,
let $\boldsymbol{F}=(F,u)$ be arbitrary. If $F$ is not a path then
$\boldsymbol{F}\sim_{\mathcal{W}}\boldsymbol{C}$. Indeed, for every
$\boldsymbol{K}\in\mathcal{D}(1)$, $F$ is a subgraph of
$\operatorname{soe}(\boldsymbol{K}\odot\boldsymbol{F})$. Hence, regardless of
$\boldsymbol{K}$, both $\operatorname{soe}(\boldsymbol{K}\odot\boldsymbol{F})$
and $\operatorname{soe}(\boldsymbol{K}\odot\boldsymbol{C})$ are not paths. If
$F$ is a path, then $\boldsymbol{F}$ and $\boldsymbol{1}$, $\boldsymbol{P}$,
or $\boldsymbol{Q}$ are equivalent depending on whether the degree of $u$ is
$0$, $1$, or $2$.

To show that the representatives in Figure 2 are in distinct classes, observe
for example that
$\operatorname{soe}(\boldsymbol{P}\odot\boldsymbol{P})\in\mathcal{W}$ while
$\operatorname{soe}(\boldsymbol{P}\odot\boldsymbol{Q})\not\in\mathcal{W}$,
thus $\boldsymbol{P}\not\sim_{\mathcal{W}}\boldsymbol{Q}$. Similarly,
$\operatorname{soe}(\boldsymbol{1}\odot\boldsymbol{Q})\in\mathcal{W}$ whereas
$\operatorname{soe}(\boldsymbol{P}\odot\boldsymbol{Q})\not\in\mathcal{W}$,
thus $\boldsymbol{1}\not\sim_{\mathcal{W}}\boldsymbol{P}$. ∎

A more involved example is the following:

######  Example 2.12.

Let $\mathcal{F}$ be the family of $H$-subgraph-free graph for some graph $H$.
Then $\mathcal{F}$ is $k$-recognisable for every $k\geq 1$.

###### Proof.

Suppose $H$ has $m$ vertices. For a distinctly $k$-labelled graph
$\boldsymbol{F}=(F,\boldsymbol{u})$, consider the set
$\mathcal{H}(\boldsymbol{F})$ of (isomorphism types of) distinctly
$k$-labelled graphs $\boldsymbol{F}^{\prime}=(F^{\prime},\boldsymbol{u})$
where $F^{\prime}$ is a subgraph of $F$ such that
$V(F^{\prime})\supseteq\\{u_{1},\dots,u_{k}\\}$ has at most $k+m$ vertices.
Clearly, there are only finitely many possible sets
$\mathcal{H}(\boldsymbol{F})$. Furthermore, if
$\mathcal{H}(\boldsymbol{F}_{1})=\mathcal{H}(\boldsymbol{F}_{2})$ then
$\boldsymbol{F}_{1}\sim_{\mathcal{F}}\boldsymbol{F}_{2}$. Indeed, if
$\boldsymbol{K}\in\mathcal{D}(k)$ is such that
$\operatorname{soe}(\boldsymbol{K}\odot\boldsymbol{F}_{1})$ contains $H$ as a
subgraph then so does
$\operatorname{soe}(\boldsymbol{K}\odot\boldsymbol{F}_{2})$ since
$\boldsymbol{F}_{1}$ and $\boldsymbol{F}_{2}$ contain the same distinctly
$k$-labelled graphs on at most $k+m$ vertices. ∎

Analogously, one may argue that every class defined by forbidden minors is
recognisable.

Courcelle [15] proved that every $\mathsf{CMSO}_{2}$-definable graph class is
_recognisable_ , i.e. it is $k$-recognisable for every $k\in\mathbb{N}$.
Conversely, Bojańczyk and Pilipczuk [12] proved that if a recognisable class
$\mathcal{F}$ has bounded treewidth then it is $\mathsf{CMSO}_{2}$-definable.
Furthermore, they conjecture that $k$-recognisability is a sufficient
condition for a graph class of treewidth at most $k-1$ to be
$\mathsf{CMSO}_{2}$-definable.

For our purposes, it suffices to weaken Definition 2.10 as follows: The
equivalence relation $\sim_{\mathcal{F}}$ can be defined on $\mathcal{TW}(k)$
instead of $\mathcal{G}(k)$. Then $\boldsymbol{K}$ ranges over
$\mathcal{TW}(k)$. We chose the definition from [15, 12] in order to be
aligned with the literature.

###  2.6 Cai–Fürer–Immerman Graphs

We recall the following version of the classical CFI graphs [14] from [36].
Let $G$ be a graph without isolated vertices and $U\colon
V(G)\to\mathbb{Z}_{2}$ a function from $G$ to the abelian group on two
elements $\mathbb{Z}_{2}$. For a vertex $v\in V(G)$, write $E(v)\subseteq
E(G)$ for the set of edges incident to $v$. The graph $G_{U}$ has vertices
$(v,S)$ for every $v\in V(G)$ and $S\colon E(v)\to\mathbb{Z}_{2}$ such that
$\sum_{e\in E(v)}S(e)=U(v)$. Two vertices $(u,S)$ and $(v,T)$ are adjacent in
$G_{U}$ if $uv\in E(G)$ and $S(uv)+T(uv)=0$. Note that $\lvert
V(G_{U})\rvert=\sum_{v\in V(G)}2^{\deg(v)-1}$.

By [36, Lemma 3.2], if $\sum_{v\in V(G)}U(v)=\sum_{v\in V(G)}U^{\prime}(v)$
for $U,U^{\prime}\colon V(G)\to\mathbb{Z}_{2}$ then $G_{U}=G_{U^{\prime}}$. We
may thus write $G_{0}$ and $G_{1}$ for the _even_ and the _odd_ CFI graph of
$G$. We recall the following properties:

######  Lemma 2.13 ([36, Corollary 3.7]).

Let $G$ be a connected graph and $U\colon V(G)\to\mathbb{Z}_{2}$. Then the
following are equivalent:

  1. 1.

$G_{0}\cong G_{U}$,

  2. 2.

$\sum_{v\in V(G)}U(v)=0$,

  3. 3.

$\hom(G,G_{0})=\hom(G,G_{U})$.

##  3 Decidability

As a first step, we show that the problem HomInd($\mathcal{F}$) is decidable
for every $k$-recognisable graph class $\mathcal{F}$ of treewidth at most
$k-1$. We do so by establishing a bound on the maximum size of a graph
$F\in\mathcal{F}$ for which $\hom(F,G)=\hom(F,H)$ needs to be checked in order
to conclude whether $G\equiv_{\mathcal{F}}H$.

For a graph class $\mathcal{F}$ and $\ell\in\mathbb{N}$, define the class
$\mathcal{F}_{\leq\ell}\coloneqq\\{F\in\mathcal{F}\mid|V(F)|\leq\ell\\}$.

######  Theorem 3.1.

Let $k\geq 1$. Let $\mathcal{F}$ be a graph class of treewidth $\leq k-1$ with
$k$-recognisability index $C$. For graphs $G$ and $H$ on at most $n$ vertices,

$G\equiv_{\mathcal{F}}H\iff G\equiv_{\mathcal{F}_{\leq f(n,k,C)}}H$

where $f(n,k,C)\coloneqq\max\\{k^{2Cn^{k}},2Cn^{k}\\}$.

Fix throughout a graph class $\mathcal{F}$ as in Theorem 3.1. In reminiscence
of Courcelle’s theorem, we let $Q$ denote the set of equivalence classes of
$\sim_{\mathcal{F}}$, as defined in Definition 2.10, and call them _states_. A
state $q\in Q$ is _accepting_ if for a (and equivalently, every)
$\boldsymbol{F}$ in $q$ it holds that
$\operatorname{soe}\boldsymbol{F}\in\mathcal{F}$. Write $A\subseteq Q$ for the
set of all accepting states.

The states are fine enough to distinguish between graphs in $\mathcal{F}$ and
those not in $\mathcal{F}$. Furthermore, they are preserved under series
composition and gluing, which are the operations under which all graphs in
$\mathcal{TW}(k)$ can be generated by Lemma 2.6.

######  Lemma 3.2.

For
$\boldsymbol{F},\boldsymbol{F}^{\prime},\boldsymbol{F}_{1},\boldsymbol{F}_{2},\boldsymbol{F}^{\prime}_{1},\boldsymbol{F}^{\prime}_{2}\in\mathcal{D}(k)$,
$\boldsymbol{L}\in\mathcal{D}(k,k)$,

  1. 1.

if $\boldsymbol{F}_{1}\sim_{\mathcal{F}}\boldsymbol{F}^{\prime}_{1}$ and
$\boldsymbol{F}_{2}\sim_{\mathcal{F}}\boldsymbol{F}^{\prime}_{2}$ then
$\boldsymbol{F}_{1}\odot\boldsymbol{F}_{2}\sim_{\mathcal{F}}\boldsymbol{F}^{\prime}_{1}\odot\boldsymbol{F}^{\prime}_{2}$,

  2. 2.

if $\boldsymbol{F}\sim_{\mathcal{F}}\boldsymbol{F}^{\prime}$ then
$\boldsymbol{L}\cdot\boldsymbol{F}\sim_{\mathcal{F}}\boldsymbol{L}\cdot\boldsymbol{F}^{\prime}$.

###### Proof.

Let $\boldsymbol{K}=(K,\boldsymbol{u})\in\mathcal{D}(k)$ be arbitrary. Then
$\operatorname{soe}((\boldsymbol{K}\odot\boldsymbol{F}_{1})\odot\boldsymbol{F}_{2})\in\mathcal{F}\Leftrightarrow\operatorname{soe}((\boldsymbol{K}\odot\boldsymbol{F}_{1})\odot\boldsymbol{F}^{\prime}_{2})\in\mathcal{F}\Leftrightarrow\operatorname{soe}(\boldsymbol{K}\odot\boldsymbol{F}^{\prime}_{1}\odot\boldsymbol{F}^{\prime}_{2})\in\mathcal{F}$.

For a $(k,k)$-bilabelled graph
$\boldsymbol{L}=(L,\boldsymbol{u},\boldsymbol{v})$, write
$\boldsymbol{L}^{*}\coloneqq(L,\boldsymbol{v},\boldsymbol{u})$ for the
$(k,k)$-bilabelled graph obtained by swapping the in- and out-labels. Then
$\operatorname{soe}(\boldsymbol{K}\odot(\boldsymbol{L}\cdot\boldsymbol{F}))=\operatorname{soe}((\boldsymbol{L}^{*}\cdot\boldsymbol{K})\odot\boldsymbol{F})$.
Thus the second claim follows from the first. ∎

The key observation is that since $\sim_{\mathcal{F}}$ is preserved under
these operations (Lemma 3.2) we can keep track of homomorphism counts of the
graphs in each of the states using finite-dimensional vector spaces.

Suppose wlog that $V(G)$ and $V(H)$ are disjoint. To every state $q\in Q$, we
associate vector spaces $S_{d}(q)\subseteq\mathbb{R}^{V(G)^{k}\cup V(H)^{k}}$
for $d\geq 1$. Recall that for a distinctly $k$-labelled graph
$\boldsymbol{F}\in\mathcal{D}(k)$, the vectors
$\boldsymbol{F}_{G}\in\mathbb{R}^{V(G)^{k}}$ and
$\boldsymbol{F}_{H}\in\mathbb{R}^{V(H)^{k}}$ are the homomorphism tensors of
$\boldsymbol{F}$ w.r.t. $G$ and $H$. Let
$\boldsymbol{F}_{G}\oplus\boldsymbol{F}_{H}\coloneqq\left(\begin{smallmatrix}\boldsymbol{F}_{G}\\\
\boldsymbol{F}_{H}\end{smallmatrix}\right)\in\mathbb{R}^{V(G)^{k}\cup
V(H)^{k}}$ denote the vector obtained by appending $\boldsymbol{F}_{H}$ to
$\boldsymbol{F}_{G}$ and define

$S_{d}(q)\coloneqq\left<\\{\boldsymbol{F}_{G}\oplus\boldsymbol{F}_{H}\mid\boldsymbol{F}\in\mathcal{TW}_{d}(k)\text{
in }q\\}\right>\subseteq\mathbb{R}^{V(G)^{k}\cup V(H)^{k}},$

i.e. $S_{d}(q)$ is the subspace of $\mathbb{R}^{V(G)^{k}\cup V(H)^{k}}$
spanned by the stacked homomorphism tensors
$\boldsymbol{F}_{G}\oplus\boldsymbol{F}_{H}$ for
$\boldsymbol{F}\in\mathcal{TW}_{d}(k)$ in state $q$. Clearly, $S_{d}(q)$ is a
subspace of $S_{d+1}(q)$ for every $d\geq 1$. Finally, let
$S(q)\coloneqq\bigcup_{d\geq 1}S_{d}(q)$.

Let $\mathcal{F}_{\geq k}\coloneqq\\{F\in\mathcal{F}\mid\lvert V(F)\rvert\geq
k\\}$ and write $\boldsymbol{1}_{G}$, $\boldsymbol{1}_{H}$ for the vectors in
$\mathbb{R}^{V(G)^{k}\cup V(H)^{k}}$ which are one on $V(G)^{k}$ and
$V(H)^{k}$, respectively, and zero everywhere else. The following Lemma 3.3
describes how to recover homomorphism counts from the vectors in the $S(q)$.

######  Lemma 3.3.

Two graph $G$ and $H$ are homomorphism indistinguishable over
$\mathcal{F}_{\geq k}$ if and only if for every $q\in A$ and every $v\in S(q)$
it holds that $\boldsymbol{1}_{G}^{T}v=\boldsymbol{1}_{H}^{T}v$.

###### Proof.

For the forward direction, note that $S(q)$ is spanned by the
$\boldsymbol{F}_{G}\oplus\boldsymbol{F}_{H}$ where
$\boldsymbol{F}\in\mathcal{TW}(k)$ is in $q$. Let $\boldsymbol{F}$ in $q\in A$
be arbitrary. Then $\operatorname{soe}\boldsymbol{F}\eqqcolon
F\in\mathcal{F}_{\geq k}$ and it holds that
$\boldsymbol{1}_{G}^{T}(\boldsymbol{F}_{G}\oplus\boldsymbol{F}_{H})=\operatorname{soe}(\boldsymbol{F}_{G})=\hom(F,G)=\hom(F,H)=\boldsymbol{1}_{H}^{T}(\boldsymbol{F}_{G}\oplus\boldsymbol{F}_{H})$.
Conversely, let $F\in\mathcal{F}_{\geq k}$ be arbitrary. Since
$\operatorname{tw}F\leq k-1$, by Lemma 2.2, there exists $\boldsymbol{u}\in
V(F)^{k}$ such that
$\boldsymbol{F}\coloneqq(F,\boldsymbol{u})\in\mathcal{TW}(k)$. Furthermore,
$\boldsymbol{F}$ belongs to some accepting $q\in Q$. Thus,
$\boldsymbol{F}_{G}\oplus\boldsymbol{F}_{H}\in S(q)$, and hence
$\hom(F,G)=\boldsymbol{1}_{G}^{T}(\boldsymbol{F}_{G}\oplus\boldsymbol{F}_{H})=\boldsymbol{1}_{H}^{T}(\boldsymbol{F}_{G}\oplus\boldsymbol{F}_{H})=\hom(F,H)$.
∎

The bound in Theorem 3.1 is essentially due to a dimension argument. Each of
the spaces $S(q)\subseteq\mathbb{R}^{V(G)^{k}\cup V(H)^{k}}$ is of dimension
at most $2n^{k}$. Thus, the following Lemma 3.4 yields that $S_{d}(q)=S(q)$
for $d\coloneqq 2Cn^{k}$ and all $q\in Q$.

######  Lemma 3.4.

If $d\geq 1$ is such that $S_{d}(q)=S_{d+1}(q)$ for all $q\in Q$ then
$S_{d}(q)=S(q)$ for all $q\in Q$.

###### Proof.

We argue that $S_{d}(q)\subseteq S_{d+i}(q)$ for all $i\geq 1$ by induction on
$i$. The base case holds by assumption. The space $S_{d+i+1}(q)$ is spanned by
the $\boldsymbol{F}_{G}\oplus\boldsymbol{F}_{H}$ where
$\boldsymbol{F}\in\mathcal{TW}_{d+i+1}(k)$ is in $q$. For such
$\boldsymbol{F}$, by Lemma 2.6, there exist $A\subseteq\binom{[k]}{2}$,
$L\subseteq[k]$, and $\boldsymbol{F}^{\ell}\in\mathcal{TW}_{d+i}(k)$ for
$\ell\in L$ such that

$\boldsymbol{F}=\prod_{ij\in A}\boldsymbol{A}^{ij}\cdot\bigodot_{\ell\in
L}\boldsymbol{J}^{\ell}\boldsymbol{F}^{\ell}.$

Let $q_{\ell}$ denote the state of $\boldsymbol{F}^{\ell}$. By assumption,
there exist $\boldsymbol{K}^{\ell m}\in\mathcal{TW}_{d}(k)$ in state
$q_{\ell}$ and $\alpha_{m}\in\mathbb{R}$ such that
$\boldsymbol{F}^{\ell}_{G}\oplus\boldsymbol{F}^{\ell}_{H}=\sum\alpha_{m}\boldsymbol{K}^{\ell
m}_{G}\oplus\boldsymbol{K}^{\ell m}_{H}$. By Lemma 3.2,

$\boldsymbol{F}\sim_{\mathcal{F}}\prod_{ij\in
A}\boldsymbol{A}^{ij}\cdot\bigodot_{\ell\in
L}\boldsymbol{J}^{\ell}\boldsymbol{K}^{\ell m}.$

for all $m$. Thus, $\boldsymbol{F}_{G}\oplus\boldsymbol{F}_{H}$ can be written
as linear combination of vectors in $S_{d+i}(q)\subseteq S_{d}(q)$, by
induction. ∎

This concludes the preparations for the proof of Theorem 3.1.

###### Proof of Theorem 3.1.

It suffices to prove the backward implication. Since $k\leq k^{2Cn^{k}}$, it
suffices to show that $G\equiv_{\mathcal{F}_{\geq k}}H$ by verifying the
condition in Lemma 3.3. By Lemma 3.4, $S_{d}(q)=S(q)$ for $d\coloneqq 2Cn^{k}$
and all $q\in Q$. Hence, $S(q)$ is spanned by the
$\boldsymbol{F}_{G}\oplus\boldsymbol{F}_{H}$ where
$\boldsymbol{F}\in\mathcal{TW}_{d}(k)$ is in state $q$. By Lemma 2.5, these
graphs has at most $\max\\{k^{d},d\\}=\max\\{k^{2Cn^{k}},2Cn^{k}\\}$ vertices.
Thus,
$\boldsymbol{1}_{G}^{T}(\boldsymbol{F}_{G}\oplus\boldsymbol{F}_{H})=\hom(\operatorname{soe}\boldsymbol{F},G)=\hom(\operatorname{soe}\boldsymbol{F},H)=\boldsymbol{1}_{H}^{T}(\boldsymbol{F}_{G}\oplus\boldsymbol{F}_{H}),$
as desired. ∎

Finally, we adapt the techniques developed above to prove the following
analogue of Theorem 3.1 for graph classes of bounded pathwidth:

######  Theorem 3.5.

Let $k\geq 1$. Let $\mathcal{F}$ be a graph class of pathwidth $\leq k-1$ with
$k$-recognisability index $C$. For graphs $G$ and $H$ on at most $n$ vertices,

$G\equiv_{\mathcal{F}}H\iff G\equiv_{\mathcal{F}_{\leq f(n,k,C)}}H$

where $f(n,k,C)\coloneqq 2Cn^{k}+k-1$.

###### Proof.

We sketch how the proof of Theorem 3.1 needs to be adapted. Define $S_{d}(q)$
and $S(q)$ as above with $\mathcal{PW}_{d}(k)$ instead of
$\mathcal{TW}_{d}(k)$, cf. Section 2.3.

By Lemma 2.9, Observing that for every
$\boldsymbol{F}\in\mathcal{PW}_{d+1}(k)$ there exists
$A\subseteq\binom{[k]}{2}$, $\ell\in[k]$, and
$\boldsymbol{F}^{\prime}\in\mathcal{PW}_{d}(k)$ such that
$\boldsymbol{F}=\boldsymbol{A}\boldsymbol{J}^{\ell}\boldsymbol{F}^{\prime}$
where $\boldsymbol{A}\coloneqq\prod_{ij\in A}\boldsymbol{A}^{ij}$, Lemma 3.4
follows analogously. Thus, $S_{d}(q)=S(q)$ for all $q\in Q$ when $d\coloneqq
2Cn^{k}$. By Lemma 2.8, this space is spanned by homomorphism tensors of
graphs of size at most $2Cn^{k}+k-1$. The statement follows as in Theorem 3.1.
∎

Given Theorems 3.1 and 3.5, we suggest to consider the following general
question: For a graph class $\mathcal{F}$, is there a function
$f\colon\mathbb{N}\to\mathbb{N}$ such that $G\equiv_{\mathcal{F}}H$ if and
only if $G\equiv_{\mathcal{F}_{\leq f(n)}}H$ for all graphs $G$ and $H$ on at
most $n$ vertices? If such an $f$ exists, can be computed, and if membership
in $\mathcal{F}$ is decidable then HomInd($\mathcal{F}$) is decidable.

Theorems 3.1 and 3.5 give such functions for every recognisable graph class of
bounded treewidth. By [30], for the class $\mathcal{G}$ of all graphs, $f$ can
be taken to be the identity $n\mapsto n$. By [32], there exists no such
function for the class of all planar graphs $\mathcal{P}$ which is computable.

##  4 Modular Homomorphism Indistinguishability in Polynomial Time

The insight that yielded Theorem 3.1 is that the spaces $S(q)$ have polynomial
dimension. In this section, we strengthen this result by showing that bases
$B(q)$ for the spaces $S(q)$ can be efficiently computed. A technical
difficulty arising here is that the numbers produced in the process can be of
doubly exponential magnitude. In order to overcome this problem, we first
consider the following problem:

ModHomInd($\mathcal{F}$)
Input: Graphs $G$ and $H$, a prime $p$ in binary Question: Are $G$ and $H$
homomorphism indistinguishable over $\mathcal{F}$ modulo $p$?

It is easy to see that Lemmas 3.3 and 3.4 also hold when constructing the
vector spaces over the finite field $\mathbb{F}_{p}$. Doing this has the
advantage that all arithmetic operations can be carried out in $(\log
p)^{O(1)}$. We prove the following:

######  Theorem 4.1.

Let $k\geq 1$. If $\mathcal{F}$ is a $k$-recognisable graph class of treewidth
$\leq k-1$ then ModHomInd($\mathcal{F}$) is in polynomial time.

For later reference, we recall the data describing the graph class
$\mathcal{F}$ which the algorithm utilises. Recall $Q$ the set of equivalence
classes (_states_) of $\sim_{\mathcal{F}}$ and $A\subseteq Q$ the set of
accepting states from Section 3. Lemma 3.2 asserts that the operations
generating $\mathcal{TW}(k)$ can be regarded as operations on the equivalence
classes of $\sim_{\mathcal{F}}$. The algorithm is provided with a table
encoding how each of the operation acts on the states.

Write $\pi\colon\mathcal{TW}(k)\to Q$ for the map that associates an
$\boldsymbol{F}\in\mathcal{TW}(k)$ to its state $q\in Q$. Write $q_{0}$ for
the state of $\boldsymbol{1}\in\mathcal{TW}(k)$. Furthermore, write $g\colon
Q\times Q\to Q$ and $b_{\boldsymbol{B}}\colon Q\to Q$ for every
$\boldsymbol{B}\in\mathcal{B}(k)$ such that

$\displaystyle g(\pi(\boldsymbol{F}),\pi(\boldsymbol{F}^{\prime}))$
$\displaystyle=\pi(\boldsymbol{F}\odot\boldsymbol{F}^{\prime}),$ (1)
$\displaystyle b_{\boldsymbol{B}}(\pi(\boldsymbol{F}))$
$\displaystyle=\pi(\boldsymbol{B}\cdot\boldsymbol{F}).$ (2)

for every $\boldsymbol{F},\boldsymbol{F}^{\prime}\in\mathcal{TW}(k)$ and
$\boldsymbol{B}\in\mathcal{B}(k)$. Note that $Q$, $A$, $g$, $q_{0}$ and the
$b_{\boldsymbol{B}}$, $\boldsymbol{B}\in\mathcal{B}(k)$, are finite objects,
which can be hard-coded. The map $\pi$ does not need to be computable and is
only needed for analysing the algorithm.

Finally, for a set $B\subseteq\mathbb{F}_{p}^{n}$, write
$\left<B\right>\subseteq\mathbb{F}_{p}^{n}$ for the $\mathbb{F}_{p}$-vector
space spanned by $B$, cf. Algorithms 1 and 1. Having defined all necessary
notions, we can now describe Algorithm 1.

Input: graphs $G$ and $H$, a prime $p$ in binary.

Data: $k$, $Q$, $A$, $q_{0}$, $g$, $b_{\boldsymbol{B}}$ for
$\boldsymbol{B}\in\mathcal{B}(k)$.

Output: whether $G\equiv_{\mathcal{F}}^{p}H$.

1

2 With brute force check whether $G$ and $H$ are homomorphism
indistinguishable over the finite graph class $\mathcal{F}_{\leq k}$ modulo
$p$ and reject if not;

3

4$B(q_{0})\leftarrow\\{\boldsymbol{1}_{G}\oplus\boldsymbol{1}_{H}\\}\subseteq\mathbb{F}_{p}^{V(G)^{k}\cup
V(H)^{k}}$;

5

6$B(q)\leftarrow\emptyset\subseteq\mathbb{F}_{p}^{V(G)^{k}\cup V(H)^{k}}$ for
all $q\neq q_{0}$;

7

8repeat

9

10 foreach  _$\boldsymbol{B}\in\mathcal{B}(k)$ , $q\in Q$, $v\in B(q)$_ do

11
$w\leftarrow(\boldsymbol{B}_{G}\oplus\boldsymbol{B}_{H})v\coloneqq\left(\begin{smallmatrix}\boldsymbol{B}_{G}&0\\\
0&\boldsymbol{B}_{H}\end{smallmatrix}\right)v$;

12

13 if  _$w\not\in\left <B(b_{\boldsymbol{B}}(q))\right>$_ then

14 add $w$ to $B(b_{\boldsymbol{B}}(q))$;

15 foreach  _$q_{1},q_{2}\in Q$ , $v_{1}\in B(q_{1})$, $v_{2}\in B(q_{2})$_ do

16 $w\leftarrow v_{1}\odot v_{2}$;

17 if  _$w\not\in\left <B(g(q_{1},q_{2}))\right>$_ then

18 add $w$ to $B(g(q_{1},q_{2}))$;

19until  _none of the $B(q)$, $q\in Q$, are updated_;

20if  _ $\boldsymbol{1}_{G}^{T}v=\boldsymbol{1}_{H}^{T}v$ for all $q\in A$ and
$v\in B(q)$ _ then

21 accept;

22else

23 reject;

Algorithm 1 ModHomInd($\mathcal{F}$) for $k$-recognisable $\mathcal{F}$ of
treewidth $\leq k-1$.

Write $n\coloneqq\max\\{|V(G)|,|V(H)|\\}$ and $C\coloneqq|Q|$. The runtime of
Algorithm 1 can be analysed as follows:

######  Lemma 4.2.

There exists a computable function $f$ such that Algorithm 1 runs in time
$f(k,C)n^{O(k)}(\log p)^{O(1)}$.

###### Proof.

Consider the following individual runtimes:

Counting homomorphism of a graph on $k$ vertices into a graph on $n$ vertices,
can be done in time $n^{k}$. Hence, Algorithm 1 requires time $f(k)n^{k}$ for
some computable $f$.

Throughout the execution of Algorithm 1, the vectors in each $B(q)$, $q\in Q$,
are linearly independent. Thus, $|B(q)|\leq\dim S(q)\leq 2n^{k}$ and
$\sum_{q\in Q}|B(q)|\leq 2Cn^{k}$. Hence, the body of the loop in Algorithm 1
is entered at most $2Cn^{k}$ many times.

The loop in Algorithm 1 iterates over at most $k^{2}\cdot C\cdot 2n^{k}$ many
objects. Computing the vector $w$ takes polynomial time in $2n^{k}\cdot\log
p$. The same holds for checking the condition in Algorithms 1 and 1, e.g. via
Gaussian elimination. The loop in Algorithm 1 iterates over at most
$C^{2}\cdot(2n^{k})^{2}$ many objects.

Finally, checking the condition in Algorithm 1 takes $C\cdot 2n^{k}\cdot(\log
p)^{O(1)}$ many steps. ∎

The following Lemma 4.3 yields that Algorithm 1 is correct.

######  Lemma 4.3.

When Algorithm 1 terminates, $B(q)$ spans $S(q)$ for all $q\in Q$.

###### Proof.

First observe that the invariant $B(q)\subseteq S(q)$ for all $q\in Q$ is
preserved throughout Algorithm 1. Indeed, for example in Algorithm 1, since
$v\in B(q)\subseteq S(q)$, it can be written as linear combination of
$\boldsymbol{F}_{G}\oplus\boldsymbol{F}_{H}$ for
$\boldsymbol{F}\in\mathcal{TW}(k)$ of state $q$. Because
$\boldsymbol{B}\cdot\boldsymbol{F}$ is in state $b_{\boldsymbol{B}}(q)$ by
Equation 2, $(\boldsymbol{B}_{G}\oplus\boldsymbol{B}_{H})v$ is in the span of
$\boldsymbol{B}_{G}\boldsymbol{F}_{G}\oplus\boldsymbol{B}_{H}\boldsymbol{F}_{H}\in
S(b_{\boldsymbol{B}}(q))$.

Now consider the converse inclusion. The proof is by induction on the
structure in Lemma 2.6. By initialisation,
$\boldsymbol{1}_{G}\oplus\boldsymbol{1}_{H}$ is in the span of $B(q_{0})$.

For the inductive step, suppose that $\boldsymbol{F}\in\mathcal{TW}(k)$ of
state $q$ is such that $\boldsymbol{F}_{G}\oplus\boldsymbol{F}_{H}=\sum_{v\in
B(q)}\alpha_{v}v$ for some coefficients $\alpha_{v}\in\mathbb{F}_{p}$. Let
$\boldsymbol{B}\in\mathcal{B}(k)$ and
$\boldsymbol{F}^{\prime}\coloneqq\boldsymbol{B}\cdot\boldsymbol{F}$. Then
$(\boldsymbol{B}_{G}\oplus\boldsymbol{B}_{H})v$ is in the span of
$B(b_{\boldsymbol{B}}(q))$ for all $v\in B(q)$ by the termination condition.
Hence,
$\boldsymbol{F}^{\prime}_{G}\oplus\boldsymbol{F}^{\prime}_{H}=\sum_{v\in
B(q)}\alpha_{v}(\boldsymbol{B}_{G}\oplus\boldsymbol{B}_{H})v$ is in the span
of $B(b_{\boldsymbol{B}}(q))$.

Let $\boldsymbol{F}^{1},\boldsymbol{F}^{2}\in\mathcal{TW}(k)$ of states
$q_{1},q_{2}$ be such that
$\boldsymbol{F}^{1}_{G}\oplus\boldsymbol{F}^{1}_{H}=\sum_{v\in
B(q_{1})}\alpha_{v}v$ and
$\boldsymbol{F}^{2}_{G}\oplus\boldsymbol{F}^{2}_{H}=\sum_{w\in
B(q_{2})}\beta_{w}w$ for some coefficients
$\alpha_{v},\beta_{w}\in\mathbb{F}_{p}$. Since the algorithm terminated, all
$v\odot w$ for $v\in B(q_{1})$ and $w\in B(q_{2})$ are in the span of
$B(g(q_{1},q_{2}))$. Then
$(\boldsymbol{F}^{1}\odot\boldsymbol{F}^{2})_{G}\oplus(\boldsymbol{F}^{1}\odot\boldsymbol{F}^{2})_{H}=(\boldsymbol{F}^{1}_{G}\oplus\boldsymbol{F}^{1}_{H})\odot(\boldsymbol{F}^{2}_{G}\oplus\boldsymbol{F}^{2}_{H})=\sum_{v\in
B(q_{1}),w\in B(q_{2})}\alpha_{v}\beta_{w}(v\odot w)$ is in the span of
$B(g(q_{1},q_{2}))$. ∎

This concludes the preparations for the proof of Theorem 4.1:

###### Proof of Theorem 4.1.

Lemma 4.3 implies that the conditions in Lemmas 3.3 and 1 are equivalent.
Thus, $G$ and $H$ are homomorphism indistinguishable over $\mathcal{F}_{\geq
k}$ modulo $p$ if and only if Algorithm 1 holds. The runtime bound is given in
Lemma 4.2. ∎

##  5 Polynomial Time for Bounded Pathwidth

In this section, we deduce Theorem 1.3 from Theorems 4.1 and 3.5. The idea is
to run Algorithm 1 for a collection of primes whose product is larger than any
relevant homomorphism count and invoking the Chinese Remainder Theorem. The
bound in Theorem 3.5 is tight enough for this procedure to be in polynomial
time. First consider the following Lemma 5.1.

######  Lemma 5.1.

Let $N,n\in\mathbb{N}$ be such that $N\log n\geq e^{2000}$. Let $\mathcal{F}$
be a graph class and $G$ and $H$ be graphs on at most $n$ vertices. If
$G\not\equiv_{\mathcal{F}_{\leq N}}H$ then there exists a prime $N\log
n<p\leq(N\log n)^{2}$ such that $G\not\equiv^{p}_{\mathcal{F}_{\leq N}}H$.

###### Proof.

By Fact 2.1, the product $M$ of the primes $N\log n\leq p<(N\log n)^{2}$ is at
least $2^{(N\log n)^{2}/2}>2^{N\log n}=n^{N}$. If
$G\not\equiv_{\mathcal{F}_{\leq N}}H$ then there exist $F\in\mathcal{F}_{\leq
N}$ such that $\hom(F,G)\neq\hom(F,H)$. Both numbers are non-negative and at
most $n^{N}$. Hence, $\hom(F,G)\not\equiv\hom(F,H)\mod M$. By the Chinese
Reminder Theorem [34, Theorem 2.10], there exists $N\log n<p\leq(N\log n)^{2}$
such that $\hom(F,G)\not\equiv\hom(F,H)\mod p$, as desired. ∎

We can now deduce Theorem 1.3: *

###### Proof.

Let $G$ and $H$ be graphs on at most $n$ vertices. By Theorem 3.5,
$G\equiv_{\mathcal{F}}H$ if and only if $G\equiv_{\mathcal{F}_{\leq N}}H$ for
$N\coloneqq 2Cn^{k}+k-1$. We may assume wlog that $N\log n\geq e^{2000}$. By
Lemma 5.1, the latter holds if and only if $G\equiv^{p}_{\mathcal{F}_{\leq
N}}H$ for all primes $N\log n<p\leq(N\log n)^{2}$. Moreover,
$G\equiv_{\mathcal{F}}H$ implies $G\equiv^{p}_{\mathcal{F}}H$, which implies
$G\equiv^{p}_{\mathcal{F}_{\leq N}}H$, for all primes $p$. Hence,
$G\equiv_{\mathcal{F}}H$ if and only if $G\equiv^{p}_{\mathcal{F}}H$ for all
primes $N\log n<p\leq(N\log n)^{2}$. Thus, $G\equiv_{\mathcal{F}}H$ can be
checked by enumerating all numbers between $N\log n$ and $(N\log n)^{2}$ and
running Algorithm 1 for every prime [3]. ∎

Similarly, Lemma 5.1 places HomInd($\mathcal{F}$) for a $k$-recognisable graph
class $\mathcal{F}$ of treewidth at most $k-1$ in coNP. Indeed, by Theorem
3.1, $N$ can be taken to be exponential in $n$. Thus, the prime from Lemma 5.1
is a polynomial-size certificate for $G\not\equiv_{\mathcal{F}}H$ which can be
verified in polynomial time by Theorem 4.1.

##  6 Randomised Polynomial Time

The chance that a random prime $p$ of appropriate size certifies that
$G\not\equiv_{\mathcal{F}}H$ as in Lemma 5.1 is very high. This observation
yields Theorem 1.1 via the following Lemma 6.1:

######  Lemma 6.1.

Let $N,n\in\mathbb{N}$ be such that $N\log n\geq e^{2000}$. Let $\mathcal{F}$
be a graph class and $G$ and $H$ be graphs on at most $n$ vertices. If
$G\not\equiv_{\mathcal{F}_{\leq N}}H$ then the probability that a random prime
$N\log n<p\leq(N\log n)^{2}$ is such that $G\equiv^{p}_{\mathcal{F}_{\leq
N}}H$ is at most $\frac{2}{N\log n}$.

###### Proof.

By assumption, there exist $F\in\mathcal{F}_{\leq N}$ such that
$\hom(F,G)\neq\hom(F,H)$. Both numbers are non-negative and at most $n^{N}$.
Thus, $\hom(F,G)\not\equiv\hom(F,H)\mod n^{N}$.

By the Chinese Reminder Theorem [34, Theorem 2.10], in every set $X$ of at
least $\frac{N\log n}{\log(N\log n)}$ many primes $N\log n<p\leq(N\log
n)^{2}$, there exists a $p\in X$ such that $\hom(F,G)\not\equiv\hom(F,H)\mod
p$. This is because $\prod_{p\in X}p>(N\log n)^{\frac{N\log n}{\log(N\log
n)}}=n^{N}$.

By Fact 2.1, the probability that a random prime $N\log n<p\leq(N\log n)^{2}$
is such that $\hom(F,G)\equiv\hom(F,H)\mod p$ is

$\leq\frac{N\log n}{\log(N\log n)}\cdot\frac{2\log(N\log n)}{(N\log
n)^{2}}=\frac{2}{N\log n}.$

Since $G\equiv_{\mathcal{F}}^{p}H$ implies that $\hom(F,G)\equiv\hom(F,H)\mod
p$, the desired probability is bounded by the same value. ∎

The algorithm that yields Theorem 1.1 can now be stated as Algorithm 2.

*

###### Proof.

Let $N\coloneqq\max\\{k^{2Cn^{k}},2Cn^{k}\\}$ be the quantity from Theorem
3.1. We may suppose that $N\log n\geq e^{2000}$. Since $\log N$ is polynomial
in the input size, Algorithm 2 runs in polynomial time, requiring a
polynomial-time primality test [3].

For correctness, first observe that if $G\equiv_{\mathcal{F}}H$ then Algorithm
1 always accepts. If $G\not\equiv_{\mathcal{F}}H$ then Algorithm 1 might
accept incorrectly. In each iteration, the probability of not rejecting is the
probability of not sampling a prime plus the probability of $p$ being such
that $G\equiv_{\mathcal{F}}^{p}H$. By Facts 2.1 and 6.1, it is at most

$1-\frac{1}{2\log(N\log n)}+\frac{2}{N\log n}\leq 1-\frac{1}{4\log(N\log n)}.$

By [1, 4.2.30], the total probability for accepting if
$G\not\equiv_{\mathcal{F}}H$ is at most $e^{-1}<1/2$. ∎

Input: graphs $G$ and $H$

Output: whether $G\equiv_{\mathcal{F}}H$

$n\leftarrow\max\\{|V(G)|,|V(H)|\\}$;

$N\leftarrow\max\\{k^{2Cn^{k}},2Cn^{k}\\}$;

for  _$\lceil 4\log(N\log n)\rceil$ times_ do

Sample a random number $N\log n<p<(N\log n)^{2}$;

if  _$p$ is a prime and $G\not\equiv_{\mathcal{F}}^{p}H$_ then

reject;

accept;

Algorithm 2 A randomised reduction from HomInd($\mathcal{F}$) to
ModHomInd($\mathcal{F}$) for $k$-recognisable graph classes $\mathcal{F}$ of
treewidth $\leq k-1$.

##  7 Fixed-Parameter Tractability

In this section, we deduce Theorem 1.2 from Theorem 1.1. The challenge is to
efficiently compute from the $\mathsf{CMSO}_{2}$-sentence $\varphi$ and $k$
the data describing the graph class $\mathcal{F}_{\varphi,k}$ for Algorithm 1.
That this can be done was proven by Courcelle [16].

More precisely, Courcelle proved that for every $\mathsf{CMSO}_{2}$-sentence
$\varphi$ and integer $k$ one can compute a finite automaton processing
expressions which encode (tree decompositions of) graphs of bounded treewidth.
It is this automaton from which the data required by Algorithm 1 can be
constructed. In order to state this argument precisely with minimal technical
overhead, we introduce the following syntactical counterpart of
$\mathcal{TW}(k)$.

Write $\mathfrak{TW}(k)$ for the set of _terms_ defined inductively as the
following formal expressions:

  1. 1.

$\boldsymbol{1}\in\mathcal{TW}(k)$ is a term,

  2. 2.

if $t_{1},t_{2}\in\mathfrak{TW}(k)$ then $t_{1}\odot
t_{2}\in\mathfrak{TW}(k)$,

  3. 3.

if $t\in\mathfrak{TW}(k)$ then $\boldsymbol{B}\cdot t\in\mathfrak{TW}(k)$ for
every $\boldsymbol{B}\in\mathcal{B}(k)$.

The key difference between $\mathcal{TW}(k)$ and $\mathfrak{TW}(k)$ is that
for elements of the former the tree decomposition satisfying Definition 2.4 is
implicit. For applying Courcelle’s techniques, we require this decomposition
to be explicit, as in $\mathfrak{TW}(k)$.

There is a mapping
$\operatorname{val}\colon\mathfrak{TW}(k)\to\mathcal{TW}(k)$ interpreting the
formal expressions above as concrete distinctly $k$-labelled graphs. By Lemma
2.6, this mapping is surjective. We require the following Theorem 7.1.

######  Theorem 7.1 (Courcelle).

Given a $\mathsf{CMSO}_{2}$-sentence $\varphi$ and an integer
$k\in\mathbb{N}$, one can compute a finite set $Q$, a subset $A\subseteq Q$,
an element $q_{0}\in Q$, and functions $g\colon Q\times Q\to Q$ and
$b_{\boldsymbol{B}}\colon Q\to Q$ for every $\boldsymbol{B}\in\mathcal{B}(k)$
such that there exists a map $\pi\colon\mathfrak{TW}(k)\to Q$ satisfying

  1. 1.

$\pi(\boldsymbol{1})=q_{0}$,

  2. 2.

for $t\in\mathfrak{TW}(k)$,
$\operatorname{soe}(\operatorname{val}(t))\models\varphi$ iff $\pi(t)\in A$,

  3. 3.

for all $t_{1},t_{2}\in\mathfrak{TW}(k)$, $\pi(t_{1}\odot
t_{2})=g(\pi(t_{1}),\pi(t_{2}))$,

  4. 4.

for all $t\in\mathfrak{TW}(k)$ and $\boldsymbol{B}\in\mathcal{B}(k)$,
$\pi(\boldsymbol{B}\cdot t)=b_{\boldsymbol{B}}(\pi(t))$.

###### Proof.

We sketch how the theorem follows from results in [16]. By the proof of [16,
Theorem 6.3], one can compute, given $\varphi$ and $k$, a finite deterministic
automaton recognising whether a so called $F^{\textup{HR}}_{[k]}$-term
evaluates to a graph satisfying $\varphi$.

$F^{\textup{HR}}_{[k]}$ plays the role of $\mathfrak{TW}(k)$. It is a many-
sorted signature [16, Definition 2.123] whose sorts correspond to the sources
(labels, in our terminology) of sourced (distinctly labelled) graphs of
bounded treewidth. The operations of $F^{\textup{HR}}_{[k]}$ are gluing,
dropping of labels, and renaming of labels [16, Definition 2.32]. Note that
the series product, gluing, and unlabelling from Section 2.1 can be derived
from these. Moreover, our graph $\boldsymbol{1}\in\mathcal{TW}(k)$ in Figure
1(a) can be derived from the constants in $F^{\textup{HR}}_{[k]}$.

A finite deterministic automaton processing $F^{\textup{HR}}_{[k]}$-terms [16,
Defition 3.46] comprises a finite set of states $Q$, a set of accepting states
$A\subseteq Q$, and a transition function $\delta$ mapping
$(q_{1},\dots,q_{\ell},f)$ to $q$ where $q_{1},\dots,q_{\ell},q\in Q$ and
$f\in F^{\textup{HR}}_{[k]}$ is an $\ell$-ary operation, $\ell\geq 0$.
Furthermore, there is map $\sigma$ that associates to every $q\in Q$ a sort,
that is a subset of $[k]$ of labels.

The automaton processes $F^{\textup{HR}}_{[k]}$-terms, which in our case are
elements of $\mathfrak{TW}(k)$. In order to derive the desired objects from
this automaton, we keep those states for which $\sigma$ evaluates to $[k]$.
The maps $g$ and $b_{\boldsymbol{B}}$ can be computed from $\delta$. We mark a
state $q$ as accepting if $\delta$ maps $q$ and $\operatorname{soe}$ (an
operation derived from those in $F^{\textup{HR}}_{[k]}$) to an accepting
state. The state $q_{0}$ is the state produced by $\delta$ on the $0$-ary
derived function $\boldsymbol{1}$. The map $\pi$ (which we do not require to
be computable) is defined by the semantics of the automaton. ∎

Equipped with Theorem 7.1, we prove Theorem 1.2.

*

###### Proof.

Let $\mathcal{F}\coloneqq\mathcal{F}_{\varphi,k}$. Invoking Theorem 7.1,
compute $Q$, $A$, $q_{0}$, $g$, and $b_{\boldsymbol{B}}$ for
$\boldsymbol{B}\in\mathcal{B}(k)$ in time only depending on $\varphi$ and $k$.
Now invoke Algorithm 2, which calls Algorithm 1.

Since the data obtained from Theorem 7.1 describes an equivalence relation
$t_{1}\sim t_{2}$ iff $\pi(t_{1})=\pi(t_{2})$ on $\mathfrak{TW}(k)$ rather
than on $\mathcal{TW}(k)$ as in Sections 4 and 3, the definitions in these
sections need to be slightly adapted.

By Theorem 7.1, the following assertions analogous to Lemma 3.2 hold: If
$\pi(t_{1})=\pi(t_{2})$ and $\pi(t^{\prime}_{1})=\pi(t^{\prime}_{2})$ for
$t_{1},t_{2},t^{\prime}_{1},t^{\prime}_{2}\in\mathfrak{TW}(k)$ then
$\pi(t_{1}\odot
t^{\prime}_{1})=g(\pi(t_{1}),\pi(t^{\prime}_{1}))=g(\pi(t_{2}),\pi(t^{\prime}_{2}))=\pi(t_{1}\odot
t^{\prime}_{1})$. Furthermore, for $\boldsymbol{B}\in\mathcal{B}(k)$,
$\pi(\boldsymbol{B}\cdot
t_{1})=b_{\boldsymbol{B}}(\pi(t_{1}))=b_{\boldsymbol{B}}(\pi(t_{2}))=\pi(\boldsymbol{B}\cdot
t_{2})$.

Define $S(q)$ for $q\in Q$ as the $\mathbb{F}_{p}$-vector space spanned by the
$\boldsymbol{F}_{G}\oplus\boldsymbol{F}_{H}$ where
$\boldsymbol{F}=\operatorname{val}(t)$ for some $t\in\mathfrak{TW}(k)$ in
state $q$.

Then the following analogue of Lemma 3.3 holds: Two graphs $G$ and $H$ are
homomorphism indistinguishable over $\mathcal{F}_{\geq k}$ modulo $p$ if and
only if $\boldsymbol{1}_{G}^{T}v=\boldsymbol{1}_{H}^{T}v$ for every $v\in
S(q)$ and $q\in A$. Indeed, if $F\in\mathcal{F}_{\geq k}$ then there there
exist by Theorem 7.1 a $t\in\mathfrak{TW}(k)$ such that
$\operatorname{soe}(\boldsymbol{F})\cong F$ for
$\boldsymbol{F}\coloneqq\operatorname{val}(t)$. Then
$\hom(F,G)\equiv\boldsymbol{1}_{G}^{T}(\boldsymbol{F}_{G}\oplus\boldsymbol{F}_{H})\mod
p$. The claim follows as in Lemma 3.3.

The proof of Lemma 4.3 goes through analogously, replacing structural
induction on $\mathcal{TW}(k)$ via Lemma 2.6 by structural induction on the
definition of $\mathfrak{TW}(k)$. The same holds for Lemma 3.3. Finally, Lemma
4.2 gives the desired runtime. ∎

Analogously, the following Theorem 7.2 can be derived from Theorem 1.3. The
difference between the problems PWHomInd and HomInd is that treewidth is
replaced by pathwidth.

PWHomInd
Input: Graphs $G$, $H$, a $\mathsf{CMSO}_{2}$-sentence $\varphi$, an integer
$k$. Parameter: $|\varphi|+k$. Question: Are $G$ and $H$ homomorphism
indistinguishable over $\mathcal{F}_{\varphi,k}\coloneqq\\{\text{graph }F\mid
F\models\varphi\text{ and }\operatorname{pw}F\leq k-1\\}$?

Theorem 7.2 places PWHomInd in the parametrised complexity class XP.

######  Theorem 7.2.

There exists a computable function $f\colon\mathbb{N}\to\mathbb{N}$ and a
deterministic algorithm for PWHomInd of runtime $f(|\varphi|+k)n^{O(k)}$.

###### Proof.

The desired algorithm can be obtained as described in Theorem 1.2 disregarding
the gluing operation. By Theorem 3.5, the relevant numbers are not too large
and all necessary modulo can be computed explicitly as in Theorem 1.3. ∎

##  8 Lasserre in Polynomial Time

By phrasing graph isomorphism as an integer program, heuristics from integer
programming can be used to attempt to solve graph isomorphism. Prominent
heuristics are the Sherali–Adams linear programming hierarchy and the Lasserre
semidefinite programming hierarchy. While the (approximate) feasibility of
each level of these hierarchies can be decided efficiently, it is known that a
linear number of levels is required to decide graph isomorphism for all graphs
[5, 26, 37].

In [37], for each $t\geq 1$, feasibility of the $t$-th level of the Lasserre
hierarchy was characterised as homomorphism indistinguishability relation over
a graph class $\mathcal{L}_{t}$ constructed ibidem. Moreover, the authors
asked whether there is a polynomial-time algorithm for deciding these
relations. In this section, we give a randomised algorithm for this problem
which is polynomial-time for every level.

The Lasserre semidefinite program can be solved approximately in polynomial
time using e.g. the ellipsoid method. How to decide _exact_ feasibility is
generally unknown. Since $\mathcal{L}_{t}$ is a minor-closed graph class of
treewidth at most $3t-1$, Theorem 1.1 immediately yields a randomised
polynomial-time algorithm for each level of the hierarchy. However, it is not
clear how to compute the data in Theorem 7.1 for $\mathcal{L}_{t}$ given $t$.
The following Theorem 8.1 overcomes this problem by making the dependence on
the parameter $t$ effective:

Lasserre
Input: Graphs $G$ and $H$, an integer $t\in\mathbb{N}$. Question: Is the
level-$t$ Lasserre relaxation for the standard integer program for $G\cong H$
feasible?

######  Theorem 8.1.

There exists a computable function $f\colon\mathbb{N}\to\mathbb{N}$ and a
randomised algorithm deciding Lasserre which always runs in time
$f(t)n^{O(t)}$, accepts all YES-instances and accepts NO-instances with
probability less than one half.

By [37], deciding Lasserre amounts to deciding homomorphism
indistinguishability over the graph class $\mathcal{L}_{t}$ defined ibidem. We
recall the definition:

A $(t,t)$-bilabelled graph $\boldsymbol{A}=(A,\boldsymbol{u},\boldsymbol{v})$
is _atomic_ if all its vertices are labelled, i.e. every $v\in V(A)$ appears
among the labelled vertices $u_{1},\dots,u_{t},\allowbreak v_{1},\dots,v_{t}$.
Let $\mathcal{A}_{t}$ denote the set of all atomic graphs. The class
$\mathcal{L}_{t}$ is the closure of $\mathcal{A}_{t}$ under series
composition, parallel composition with atomic graphs, and arbitrary
permutations of the labels, i.e. the action of the symmetric group
$\mathfrak{S}_{2t}$ on the $2t$ labels.

As in Section 7, write $\mathfrak{L}_{t}$ for the following inductively
defined set of formal expressions. We simultaneously define a complexity
measure $\operatorname{depth}\colon\mathfrak{L}_{t}\to\mathbb{N}$ on this set:

  1. 1.

if $\boldsymbol{A}$ is atomic then $\boldsymbol{A}\in\mathfrak{L}_{t}$ and
$\operatorname{depth}\boldsymbol{A}\coloneqq 1$,

  2. 2.

if $w\in\mathfrak{L}_{t}$ and $\boldsymbol{A}$ is atomic then
$\boldsymbol{A}\odot w\in\mathfrak{L}_{t}$ and
$\operatorname{depth}(\boldsymbol{A}\odot w)\coloneqq\operatorname{depth}w$,

  3. 3.

if $w\in\mathfrak{L}_{t}$ and $\sigma\in\mathfrak{S}_{2t}$ then
$w^{\sigma}\in\mathfrak{L}_{t}$ and
$\operatorname{depth}(w^{\sigma})\coloneqq\operatorname{depth}w$,

  4. 4.

if $w_{1},w_{2}\in\mathfrak{L}_{t}$ then $w_{1}\cdot w_{2}\in\mathfrak{L}_{t}$
and $\operatorname{depth}(w_{1}\cdot
w_{2})\coloneqq\max\\{\operatorname{depth}w_{1},\operatorname{depth}w_{2}\\}+1$.

Clearly, each expression $w\in\mathfrak{L}_{t}$ can be associated with the
$(t,t)$-bilabelled graph $\operatorname{val}(w)\in\mathcal{L}_{t}$ it encodes.

As in Section 3, we first give an upper bound on the size of the graphs whose
homomorphism counts need to be considered in order to decide Lasserre.

######  Theorem 8.2.

For $t\geq 1$ and graphs $G$ and $H$ on at most $n$ vertices,

$G\equiv_{\mathcal{L}_{t}}H\iff G\equiv_{(\mathcal{L}_{t})_{\leq f(n,t)}}H$

where $f(n,t)\coloneqq 2t\cdot 4^{n^{2t}}$.

Towards Theorem 8.2, we make the following observations:

######  Lemma 8.3.

Let $t\geq 1$. If $w\in\mathfrak{L}_{t}$ then $\operatorname{val}(w)$ is a
bilabelled graph on at most $2t\cdot 2^{\operatorname{depth}(w)}$ vertices.

###### Proof.

The proof is by induction on the definition of $\mathfrak{L}_{t}$. If $w$ is
atomic than $\operatorname{val}(w)$ has at most $2t$ vertices and
$\operatorname{depth}(w)=1$.

If $w=\boldsymbol{A}\odot w^{\prime}$ for some atomic $\boldsymbol{A}$ then
$\operatorname{val}(w)=\boldsymbol{A}\odot\operatorname{val}(w^{\prime})$ has
at most as many vertices as $\operatorname{val}(w^{\prime})$ since all
vertices of $\boldsymbol{A}$ are labelled. This implies the claim. The case
$w=(w^{\prime})^{\sigma}$ for $\sigma\in\mathfrak{S}_{2t}$ is analogous.

If $w=w_{1}\cdot w_{2}$ then the number of vertices in $\operatorname{val}(w)$
is at most the number of vertices in $\operatorname{val}(w_{1})$ plus the
number of vertices in $\operatorname{val}(w_{2})$. This number is by induction
at most
$2t\cdot(2^{\operatorname{depth}w_{1}}+2^{\operatorname{depth}w_{2}})\leq
2t\cdot 2\cdot 2^{(\operatorname{depth}w)-1}=2t\cdot
2^{\operatorname{depth}w}$, as desired. ∎

For two graphs $G$ and $H$ on at most $n$ vertices, define $S_{d}$ for $d\geq
1$ as the subspace of $\mathbb{R}^{(V(G)^{t}\cup V(H)^{t})\times(V(G)^{t}\cup
V(H)^{t})}$ spanned by
$\boldsymbol{L}_{G}\oplus\boldsymbol{L}_{H}\coloneqq\left(\begin{smallmatrix}\boldsymbol{L}_{G}&0\\\
0&\boldsymbol{L}_{H}\end{smallmatrix}\right)$ where
$\boldsymbol{L}=\operatorname{val}(w)$ for $w\in\mathfrak{L}_{t}$ with
$\operatorname{depth}(w)\leq d$. The dimension of $S\coloneqq\bigcup_{d\geq
1}S_{d}$ is at most $2n^{2t}$. Thus, by the following Lemma 8.4, $S_{d}=S$ for
$d\coloneqq 2n^{2t}$.

######  Lemma 8.4.

If $d\geq 1$ is such that $S_{d}=S_{d+1}$ then $S_{d}=S$.

###### Proof.

We show by induction that $S_{d+i}\subseteq S_{d}$ for all $i\geq 1$. The base
case follows by assumption. For the inductive step, we argue by structural
induction that for every $w\in\mathfrak{L}_{t}$ with
$\operatorname{depth}(w)\leq d+i+1$ and
$\boldsymbol{L}\coloneqq\operatorname{val}(w)$ it holds that
$\boldsymbol{L}_{G}\oplus\boldsymbol{L}_{H}\in S_{d}$. If $w$ is atomic, then
this clearly holds. If $w=\boldsymbol{A}\odot w^{\prime}$ then by the inner
induction the homomorphism tensors of $\operatorname{val}(w^{\prime})$ is in
$S_{d}$. The Schur product of any matrix in this space with
$\boldsymbol{A}_{G}\oplus\boldsymbol{A}_{H}$ is in $S_{d}$ by definition.
Thus, the claim follows. The case $w=(w^{\prime})^{\sigma}$ for
$\sigma\in\mathfrak{S}_{2t}$ is analogous. If $w=w^{\prime}\cdot w^{\prime}$
then
$\operatorname{depth}(w^{\prime}),\operatorname{depth}(w^{\prime\prime})<\operatorname{depth}(w)\leq
d+i+1$. By the outer inductive hypothesis, $S_{d+i}\subseteq S_{d}$. Thus,
writing $\boldsymbol{L}^{\prime}\coloneqq\operatorname{val}(w^{\prime})$ and
$\boldsymbol{L}^{\prime\prime}\coloneqq\operatorname{val}(w^{\prime\prime})$,
it holds that
$\boldsymbol{L}^{\prime}_{G}\oplus\boldsymbol{L}^{\prime}_{H},\boldsymbol{L}^{\prime\prime}_{G}\oplus\boldsymbol{L}^{\prime\prime}_{H}\in
S_{d}$. Thus, writing $\boldsymbol{L}\coloneq\operatorname{val}(w)$,
$\boldsymbol{L}_{G}\oplus\boldsymbol{L}_{H}=(\boldsymbol{L}^{\prime}\boldsymbol{L}^{\prime\prime})_{G}\oplus(\boldsymbol{L}^{\prime}\boldsymbol{L}^{\prime\prime})_{H}=(\boldsymbol{L}^{\prime}_{G}\oplus\boldsymbol{L}^{\prime}_{H})(\boldsymbol{L}^{\prime\prime}_{G}\oplus\boldsymbol{L}^{\prime\prime}_{H})\in
S_{d+1}\subseteq S_{d}$. ∎

This concludes the preparations for the proof of Theorem 8.2.

###### Proof of Theorem 8.2.

By Lemma 8.4, $S_{d}=S$ for $d\coloneqq 2n^{2t}$. The space $S_{d}$ is spanned
by $\boldsymbol{L}^{i}_{G}\oplus\boldsymbol{L}^{i}_{H}$ for some
$\boldsymbol{L}^{i}\in\mathcal{L}_{t}$ on at most $2t\cdot 2^{d}$ vertices, by
Lemma 8.3. For arbitrary $\boldsymbol{F}\in\mathcal{L}_{t}$, there exist
coefficients $\alpha_{i}\in\mathbb{R}$ such that
$\boldsymbol{F}_{G}\oplus\boldsymbol{F}_{H}=\sum\alpha_{i}\boldsymbol{L}^{i}_{G}\oplus\boldsymbol{L}^{i}_{H}$.
Hence,

$\displaystyle\hom(\operatorname{soe}\boldsymbol{F},G)$
$\displaystyle=\boldsymbol{1}_{G}^{T}(\boldsymbol{F}_{G}\oplus\boldsymbol{F}_{H})\boldsymbol{1}_{G}=\sum\alpha_{i}\boldsymbol{1}_{G}^{T}(\boldsymbol{L}^{i}_{G}\oplus\boldsymbol{L}^{i}_{H})\boldsymbol{1}_{G}$
$\displaystyle=\sum\alpha_{i}\hom(\operatorname{soe}\boldsymbol{L}^{i},G)=\hom(\operatorname{soe}\boldsymbol{F},H),$

as desired. ∎

We now describe Algorithm 3 for Lasserre and prove Theorem 8.1.

Input: graphs $G$ and $H$, $t\in\mathbb{N}$, a prime $p$ in binary.

Output: whether $G\equiv_{\mathcal{L}_{t}}^{p}H$.

$B\leftarrow\\{\boldsymbol{A}_{G}\oplus\boldsymbol{A}_{H}\mid\boldsymbol{A}\in\mathcal{A}_{t}\\}\subseteq\mathbb{F}_{p}^{(V(G)^{t}\cup
V(H)^{t})\times(V(G)^{t}\cup V(H)^{t})}$;

repeat

foreach  _$\boldsymbol{A}\in\mathcal{A}_{t}$ , $v\in B$_ do

$w\leftarrow(\boldsymbol{A}_{G}\oplus\boldsymbol{A}_{H})\odot v$;

if  _$w\not\in\left <B\right>$_ then

add $w$ to $B$;

foreach  _$v_{1},v_{2}\in B$_ do

$w\leftarrow v_{1}\cdot v_{2}$;

if  _$w\not\in\left <B\right>$_ then

add $w$ to $B$;

foreach  _$1\leq i <j\leq 2t$, $v\in B$_ do

$w\leftarrow v^{(i\ j)}$;

if  _$w\not\in\left <B\right>$_ then

add $w$ to $B$;

until  _$B$ is not updated_;

if
_$\boldsymbol{1}_{G}^{T}v\boldsymbol{1}_{G}=\boldsymbol{1}_{H}^{T}v\boldsymbol{1}_{H}$
for all $v\in B$ _ then

accept;

else

reject;

Algorithm 3 Modular Lasserre.

###### Proof of Theorem 8.1.

Correctness follows as in Lemma 4.3 for Algorithm 1. For the runtime, note
that the main loop is entered at most $2n^{2t}$ times. The subloops are
entered $4t(2t-1)2n^{2t}+4n^{4t}$ times. The linear algebraic operations can
be performed in time polynomial in $2n^{2t}\log p$. Thus the algorithm has
runtime $O(t^{2}n^{Ct}(\log p)^{C})$ for some constant $C\geq 4$.

To close the gap between modular homomorphism indistinguishability over
$\mathcal{L}_{t}$ and Lasserre, invoke Lemmas 6.1 and 8.2. Algorithm 2 yields
the desired randomised algorithm with $\mathcal{F}\coloneqq\mathcal{L}_{t}$
and adjusting $N\leftarrow 2t\cdot 4^{n^{2t}}$ in the second line. ∎

##  9 Lower Bounds

In this final section, we establish two hardness results for the problem
HomInd. In both cases, we show hardness for natural families of graph classes.
The approaches are orthogonal in the sense that reduction yielding coNP-
hardness in Theorem 1.5 is from a fixed-parameter tractable problem while the
reduction yielding coW[1]-hardness in Theorem 1.4 is not polynomial time.

###  9.1 coNP-Hardness

We show that the following problem is coNP-hard.

WL
Input: Graphs $G$ and $H$, an integer $k$ Question: Are $G$ and $H$ $k$-WL
indistinguishable?

By [20, 14], $k$-WL indistinguishability coincides with homomorphism
indistinguishability over the class of graphs of treewidth at most $k$. Hence,
WL is clearly a special case of HomInd, i.e. with $\varphi$ set to true. Thus,
the following Theorem 1.5 shows that when disregarding the parametrisation
HomInd is coNP-hard under polynomial-time many-one reductions.

*

###### Proof.

For a graph $G$, write $\Delta(G)$ for its maximum vertex degree. The
following problem is NP-complete by [11, Theorem 11]:

BoundedDegreeTreewidth
Input: a graph $G$ with $\Delta(G)\leq 9$, an integer $k$ Question: Is
$\operatorname{tw}G\leq k$?

By deleting isolated vertices, we may suppose that every connected component
of $G$ contains at least two vertices. If $G$ has multiple connected
components, take one vertex from each component and connect them in a pathlike
fashion. This increases the maximum degree potentially by one but makes the
graph connected. The treewidth is invariant under this operation. Thus, we may
suppose that $G$ is connected and $\Delta(G)\leq 10$.

Given such an instance, we produce the instance $(G_{0},G_{1},k)$ of WL. Here,
$G_{0}$ and $G_{1}$ are the even and odd CFI graphs as defined in Section 2.6.

Then $G_{0}$ and $G_{1}$ are $k$-WL indistinguishable if and only if
$\operatorname{tw}G\geq k+1$. Indeed, by [14, 20] and [35, Lemma 4.4], since
$G$ is connected, if $\operatorname{tw}G\geq k+1$ then $G_{0}$ and $G_{1}$ are
$k$-WL indistinguishable. Conversely, if $\operatorname{tw}G<k+1$ then $G_{0}$
and $G_{1}$ are distinguished by $k$-WL since $\hom(G,G_{0})\neq\hom(G,G_{1})$
by Lemma 2.13 and [20].

Hence, $(G,k)$ is a YES-instance of BoundedDegreeTreewidth if and only if
$(G_{0},G_{1},k)$ is a NO-instance of WL. The graphs $G_{0}$ and $G_{1}$ are
of size $\sum_{v\in V(G)}2^{\deg(v)-1}\leq 2^{9}n$, which is polynomial in the
input. ∎

###  9.2 coW[1]-Hardness

The second hardness result concerns HomInd as a parametrised problem. Write
$\mathcal{G}_{\leq k}$ for the class of all graphs on at most $k$ vertices and
consider the following problem:

HomIndSize
Input: Graphs $G$ and $H$, an integer $k\geq 1$. Parameter: $k$ Question: Are
$G$ and $H$ homomorphism indistinguishable over the class $\mathcal{G}_{\leq
k}$?

The problem HomIndSize fixed-parameter reduces to HomInd and also to PWHomInd.
To that end, consider the first-order formula

$\varphi_{k}\coloneqq\exists x_{1}\dots\exists x_{k}\forall
y\bigvee_{i=1}^{k}(y=x_{i})$

for $k\in\mathbb{N}$. Then, a graph models $\varphi_{k}$ if and only if it has
at most $k$ vertices. Furthermore, $|\varphi_{k}|=O(k)$. Hence, transforming
the instance $(G,H,k)$ of HomIndSize to the instance $(G,H,\varphi_{k},k-1)$
of HomInd gives the desired reduction. Since $|\varphi_{k}|+k=O(k)$, Theorem
9.1 implies Theorem 1.4.

######  Theorem 9.1.

HomIndSize is coW[1]-hard under fpt-reductions. Unless ETH fails, there is no
algorithm for HomIndSize that runs in time $f(k)n^{o(k)}$ for any computable
function $f\colon\mathbb{N}\to\mathbb{N}$.

###### Proof.

The proof is by reduction from the parametrised clique problem Clique, which
is well-known to be W[1]-complete and which does not admit an
$f(k)n^{o(k)}$-time algorithm for any computable $f$ unless ETH fails [17,
Theorems 13.25, 14.21].

Let $K$ denote the $k$-vertex clique and $K_{0}$ and $K_{1}$ its even and odd
CFI graphs as defined in Section 2.6. We first observe that
$K_{0}\equiv_{\mathcal{G}_{\leq k}\setminus\\{K\\}}K_{1}$. Indeed, by [36,
Theorem 3.13], for every graph $F$, $\hom(F,K_{0})\neq\hom(F,K_{1})$ if and
only if there exists a _weak oddomorphism_ $h\colon F\to K$ as defined in [36,
Definition 3.9]. By definition, a weak oddomorphism is surjective on edges and
vertices, i.e. for every $uv\in E(K)$ there exists $u^{\prime}v^{\prime}\in
E(F)$ such that $h(u^{\prime}v^{\prime})=uv$. Hence, if
$\hom(F,K_{0})\neq\hom(F,K_{1})$ then $F$ has at least $k$ vertices and
$\binom{k}{2}$ edges. The only graph in $\mathcal{G}_{\leq k}$ matching this
description is $K$.

The reduction produces given the instance $(G,k)$ of Clique the instance
$(G\times K_{0},G\times K_{1},k)$ of HomIndSize where $K$ is the $k$-vertex
clique and $\times$ denotes the categorical product of two graphs. This
instance can be produced in fixed-parameter time. Furthermore, the parameter
$k$ is not affected by this reduction. For correctness, consider the following
cases:

If $G\times K_{0}\equiv_{\mathcal{G}_{\leq k}}G\times K_{1}$ then
$\hom(K,G)=0$. Indeed, by assumption and [31, (5.30)],

$\hom(K,G)\hom(K,K_{0})=\hom(K,G\times K_{0})=\hom(K,G\times
K_{1})=\hom(K,G)\hom(K,K_{1}).$

However, $\hom(K,K_{0})\neq\hom(K,K_{1})$ by Lemma 2.13, and thus
$\hom(K,G)=0$.

Conversely, it holds that $K_{0}\equiv_{\mathcal{G}_{\leq
k}\setminus\\{K\\}}K_{1}$ and hence also $G\times
K_{0}\equiv_{\mathcal{G}_{\leq k}\setminus\\{K\\}}G\times K_{1}$ by the
initial observation and [31, (5.30)]. Since $\hom(K,G)=0$, also $G\times
K_{0}\equiv_{\mathcal{G}_{\leq k}}G\times K_{1}$. ∎

###  9.3 Beyond Treewidth

Theorem 1.1 establishes that HomInd($\mathcal{F}$) is decidable for every
recognisable graph class of bounded treewidth. It would be desirable to give a
necessary criterion for a graph class $\mathcal{F}$ to be such that
HomInd($\mathcal{F}$) is decidable/tractable.

In this section, we note that the requirement of bounded treewidth can be
relaxed when one does not aim at a polynomial-time algorithm. In the following
Theorem 9.2, $\chi(F)$ denotes the chromatic number of $F$. A typical graph
class to which the theorem applies is the class $\mathcal{K}$ of all cliques.

######  Theorem 9.2.

Let $\varphi$ be a $\mathsf{CMSO}_{2}$-sentence and $\mathcal{F}$ the class of
all graphs satisfying $\varphi$. Suppose there exists a computable non-
decreasing function $g\colon\mathbb{N}\to\mathbb{N}$ such that
$\operatorname{tw}F\leq g(\chi(F))$ for all $F\in\mathcal{F}$. Then
$\textup{{Hom\\-Ind}}(\mathcal{F})$ is decidable.

###### Proof.

Let $n\coloneqq\max\\{|V(G)|,|V(H)|\\}$. Observe that $G\equiv_{\mathcal{F}}H$
if and only if $G\equiv_{\mathcal{F}\cap\mathcal{TW}_{g(n)}}H$. Indeed, if
$F\in\mathcal{F}$ has treewidth greater than $g(n)$ then $\chi(F)>n$. Since
$G$ and $H$ both have chromatic number at most $n$, there is neither a
homomorphism $F\to G$ nor $F\to H$. Now invoke Theorem 1.2 with input
$\varphi$ and $g(n)$. ∎

The class $\mathcal{K}$ is definable in first-order logic and has constant
clique-width. Thus, from a model checking perspective, it is a rather simple
graph class. However, as shown in [13], $\textup{{Hom\\-Ind}}(\mathcal{K})$ is
$\mathsf{C}_{=}\mathsf{P}$-hard and thus not in polynomial time unless the
polynomial hierarchy collapses. This indicates that one cannot replace
Courcelle’s graph algebras for bounded treewidth, which were used in this
work, by his graph algebras for bounded clique-width, which Courcelle uses to
prove that $\mathsf{MSO}_{1}$-model checking is fixed-parameter tractable on
classes of bounded clique-width.

##  10 Conclusion

Theorem 1.1, our central result, asserts that deciding homomorphism
indistinguishable is tractable over every recognisable graph class of bounded
treewidth. Thereby, we make the intuition precise that finite-dimensional
spaces of homomorphism tensors of graphs with a bounded number of labels are
sufficient to efficiently capture homomorphism indistinguishability.

A reasonable next step is to combine Theorem 1.1 with a hardness result giving
necessary conditions on a graph class $\mathcal{F}$ for HomInd($\mathcal{F}$)
to be undecidable. We propose the following working hypothesis:

######  Question 10.1.

Is it true that for a proper minor-closed graph class $\mathcal{F}$ the
problem HomInd($\mathcal{F}$) is decidable if and only if $\mathcal{F}$ has
bounded treewidth?

Theorem 1.1 establishes the backward implication. The only known minor-closed
graph class $\mathcal{F}$ for which HomInd($\mathcal{F}$) is undecidable, is
the class of planar graphs, as shown by Mančinska and Roberson [32]. An
affirmative answer to 10.1 would imply a conjecture of Roberson [36,
Conjecture 5] asserting that $\equiv_{\mathcal{F}}$ is not isomorphism for
every proper minor- and union-closed class $\mathcal{F}$. However, even though
the graph classes in 10.1 clearly need to satisfy some condition which rules
out pathological behaviours, it is not clear whether closure under taking
minors is the right one [36, 39].

Towards 10.1, one could try to devise reductions between
HomInd($\mathcal{F}_{1}$) and HomInd($\mathcal{F}_{2}$) for distinct (minor-
closed) graph classes $\mathcal{F}_{1}$ and $\mathcal{F}_{2}$. We are not
aware of any such reduction.

A final question with repercussions beyond the scope of this work concerns the
parametrised hardness of deciding Weisfeiler–Leman indistinguishability. If
$k$ is a made a parameter in the problem WL from Section 9.1, can one show
coW[1]-hardness or even XP-completeness, cf. [8]?

#### Acknowledgements

I was supported by the German Research Foundation (DFG) within Research
Training Group 2236/2 (UnRAVeL) and by the European Union (ERC, SymSim,
101054974).

Views and opinions expressed are however those of the author(s) only and do
not necessarily reflect those of the European Union or the European Research
Council Executive Agency. Neither the European Union nor the granting
authority can be held responsible for them.

I would like to thank Martin Grohe and Louis Härtel for fruitful discussions
and their support. In particular, I thank Martin Grohe for making me aware of
Chinese remaindering.

## References

  * [1] Milton Abramowitz and Irene A. Stegun.  Handbook of mathematical functions: with formulas, graphs, and mathematical tables.  Dover Publications, New York, 1965.
  * [2] Samson Abramsky, Tomáš Jakl, and Thomas Paine.  Discrete Density Comonads and Graph Parameters.  In Helle Hvid Hansen and Fabio Zanasi, editors, Coalgebraic Methods in Computer Science, pages 23–44, Cham, 2022. Springer International Publishing.  doi:10.1007/978-3-031-10736-8_2.
  * [3] Manindra Agrawal, Neeraj Kayal, and Nitin Saxena.  PRIMES is in P.  Annals of Mathematics, 160(2):781–793, September 2004.  doi:10.4007/annals.2004.160.781.
  * [4] Albert Atserias, Phokion G. Kolaitis, and Wei-Lin Wu.  On the Expressive Power of Homomorphism Counts.  In 36th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2021, Rome, Italy, June 29 - July 2, 2021, pages 1–13, 2021.  doi:10.1109/LICS52264.2021.9470543.
  * [5] Albert Atserias and Elitza Maneva.  Sherali-Adams Relaxations and Indistinguishability in Counting Logics.  In Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, ITCS ’12, pages 367–379, New York, NY, USA, 2012. Association for Computing Machinery.  doi:10.1145/2090236.2090265.
  * [6] Albert Atserias, Laura Mančinska, David E. Roberson, Robert Sámal, Simone Severini, and Antonios Varvitsiotis.  Quantum and non-signalling graph isomorphisms.  J. Comb. Theory, Ser. B, 136:289–328, 2019.  doi:10.1016/j.jctb.2018.11.002.
  * [7] László Babai.  Graph Isomorphism in Quasipolynomial Time [Extended Abstract].  In Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing, STOC ’16, pages 684–697, New York, NY, USA, 2016. Association for Computing Machinery.  doi:10.1145/2897518.2897542.
  * [8] Christoph Berkholz.  Lower Bounds for Existential Pebble Games and $k$-Consistency Tests.  In 2012 27th Annual IEEE Symposium on Logic in Computer Science, pages 25–34, Dubrovnik, Croatia, June 2012. IEEE.  URL: http://ieeexplore.ieee.org/document/6280421/, doi:10.1109/LICS.2012.14.
  * [9] Christoph Berkholz, Paul S. Bonsma, and Martin Grohe.  Tight Lower and Upper Bounds for the Complexity of Canonical Colour Refinement.  Theory Comput. Syst., 60(4):581–614, 2017.  doi:10.1007/s00224-016-9686-0.
  * [10] Hans L. Bodlaender.  A partial $k$-arboretum of graphs with bounded treewidth.  Theoretical Computer Science, 209(1):1–45, December 1998.  URL: https://www.sciencedirect.com/science/article/pii/S0304397597002284, doi:10.1016/S0304-3975(97)00228-4.
  * [11] Hans L. Bodlaender and Dimitrios M. Thilikos.  Treewidth for graphs with small chordality.  Discrete Applied Mathematics, 79(1-3):45–61, November 1997.  URL: https://linkinghub.elsevier.com/retrieve/pii/S0166218X97000310, doi:10.1016/S0166-218X(97)00031-0.
  * [12] Mikołaj Bojańczyk and Michał Pilipczuk.  Definability equals recognizability for graphs of bounded treewidth.  In Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, pages 407–416, New York NY USA, July 2016. ACM.  URL: https://dl.acm.org/doi/10.1145/2933575.2934508, doi:10.1145/2933575.2934508.
  * [13] Jan Böker, Yijia Chen, Martin Grohe, and Gaurav Rattan.  The Complexity of Homomorphism Indistinguishability.  In Peter Rossmanith, Pinar Heggernes, and Joost-Pieter Katoen, editors, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019), volume 138 of Leibniz International Proceedings in Informatics (LIPIcs), pages 54:1–54:13, Dagstuhl, Germany, 2019\. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.  URL: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.54, doi:10.4230/LIPIcs.MFCS.2019.54.
  * [14] Jin-Yi Cai, Martin Fürer, and Neil Immerman.  An optimal lower bound on the number of variables for graph identification.  Combinatorica, 12(4):389–410, December 1992.  doi:10.1007/BF01305232.
  * [15] Bruno Courcelle.  The monadic second-order logic of graphs. I. Recognizable sets of finite graphs.  Information and Computation, 85(1):12–75, March 1990.  URL: https://www.sciencedirect.com/science/article/pii/089054019090043H, doi:10.1016/0890-5401(90)90043-H.
  * [16] Bruno Courcelle and Joost Engelfriet.  Graph Structure and Monadic Second-Order Logic: A Language-Theoretic Approach.  Cambridge University Press, USA, 1st edition, 2012.
  * [17] Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh.  Parameterized Algorithms.  Springer International Publishing, Cham, 2015.  URL: https://link.springer.com/10.1007/978-3-319-21275-3, doi:10.1007/978-3-319-21275-3.
  * [18] Anuj Dawar, Tomás Jakl, and Luca Reggio.  Lovász-Type Theorems and Game Comonads.  In 36th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2021, Rome, Italy, June 29 - July 2, 2021, pages 1–13. IEEE, 2021.  doi:10.1109/LICS52264.2021.9470609.
  * [19] Holger Dell, Martin Grohe, and Gaurav Rattan.  Lovász Meets Weisfeiler and Leman.  45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), pages 40:1–40:14, 2018.  URL: http://drops.dagstuhl.de/opus/volltexte/2018/9044/, doi:10.4230/LIPICS.ICALP.2018.40.
  * [20] Zdeněk Dvořák.  On recognizing graphs by numbers of homomorphisms.  Journal of Graph Theory, 64(4):330–342, August 2010.  doi:10.1002/jgt.20461.
  * [21] Eva Fluck, Tim Seppelt, and Gian Luca Spitzer.  Going Deep and Going Wide: Counting Logic and Homomorphism Indistinguishability over Graphs of Bounded Treedepth and Treewidth.  In Aniello Murano and Alexandra Silva, editors, 32nd EACSL Annual Conference on Computer Science Logic (CSL 2024), volume 288 of Leibniz International Proceedings in Informatics (LIPIcs), pages 27:1–27:17, Dagstuhl, Germany, 2024. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.  URL: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2024.27, doi:10.4230/LIPIcs.CSL.2024.27.
  * [22] Martin Grohe.  Equivalence in Finite-Variable Logics is Complete for Polynomial Time.  Combinatorica, 19(4):507–532, October 1999.  URL: http://link.springer.com/10.1007/s004939970004, doi:10.1007/s004939970004.
  * [23] Martin Grohe.  Counting Bounded Tree Depth Homomorphisms.  In Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS ’20, pages 507–520, New York, NY, USA, 2020. Association for Computing Machinery.  doi:10.1145/3373718.3394739.
  * [24] Martin Grohe.  The Logic of Graph Neural Networks.  In 36th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2021, Rome, Italy, June 29 - July 2, 2021, pages 1–17. IEEE, 2021.  doi:10.1109/LICS52264.2021.9470677.
  * [25] Martin Grohe, Moritz Lichter, Daniel Neuen, and Pascal Schweitzer.  Compressing CFI Graphs and Lower Bounds for the Weisfeiler–Leman Refinements.  In 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023, Santa Cruz, CA, USA, November 6-9, 2023, pages 798–809. IEEE, 2023.  doi:10.1109/FOCS57990.2023.00052.
  * [26] Martin Grohe and Martin Otto.  Pebble Games and Linear Equations.  The Journal of Symbolic Logic, 80(3):797–844, 2015.  URL: http://www.jstor.org/stable/43864249, doi:10.1017/jsl.2015.28.
  * [27] Martin Grohe, Gaurav Rattan, and Tim Seppelt.  Homomorphism Tensors and Linear Equations.  In Mikołaj Bojańczyk, Emanuela Merelli, and David P. Woodruff, editors, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022), volume 229 of Leibniz International Proceedings in Informatics (LIPIcs), pages 70:1–70:20, Dagstuhl, Germany, 2022\. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.  URL: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.70, doi:10.4230/LIPIcs.ICALP.2022.70.
  * [28] Neil Immerman and Eric Lander.  Describing Graphs: A First-Order Approach to Graph Canonization.  In Alan L. Selman, editor, Complexity Theory Retrospective: In Honor of Juris Hartmanis on the Occasion of His Sixtieth Birthday, July 5, 1988, pages 59–81. Springer New York, New York, NY, 1990\.  doi:10.1007/978-1-4612-4478-3_5.
  * [29] Moritz Lichter, Benedikt Pago, and Tim Seppelt.  Limitations of Game Comonads for Invertible-Map Equivalence via Homomorphism Indistinguishability.  In Aniello Murano and Alexandra Silva, editors, 32nd EACSL Annual Conference on Computer Science Logic (CSL 2024), volume 288 of Leibniz International Proceedings in Informatics (LIPIcs), pages 36:1–36:19, Dagstuhl, Germany, 2024. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.  URL: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2024.36, doi:10.4230/LIPIcs.CSL.2024.36.
  * [30] László Lovász.  Operations with structures.  Acta Mathematica Academiae Scientiarum Hungarica, 18(3):321–328, September 1967.  doi:10.1007/BF02280291.
  * [31] László Lovász.  Large networks and graph limits.  Number volume 60 in American Mathematical Society colloquium publications. American Mathematical Society, Providence, Rhode Island, 2012.
  * [32] Laura Mančinska and David E. Roberson.  Quantum isomorphism is equivalent to equality of homomorphism counts from planar graphs.  In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 661–672, 2020.  doi:10.1109/FOCS46700.2020.00067.
  * [33] Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe.  Weisfeiler and Leman Go Neural: Higher-Order Graph Neural Networks.  Proceedings of the AAAI Conference on Artificial Intelligence, 33:4602–4609, July 2019.  URL: https://aaai.org/ojs/index.php/AAAI/article/view/4384, doi:10.1609/aaai.v33i01.33014602.
  * [34] Melvyn B. Nathanson.  Elementary Methods in Number Theory, volume 195 of Graduate Texts in Mathematics.  Springer New York, New York, NY, 2000.  doi:10.1007/b98870.
  * [35] Daniel Neuen.  Homomorphism-Distinguishing Closedness for Graphs of Bounded Tree-Width, April 2023.  URL: http://arxiv.org/abs/2304.07011.
  * [36] David E. Roberson.  Oddomorphisms and homomorphism indistinguishability over graphs of bounded degree, June 2022.  URL: http://arxiv.org/abs/2206.10321.
  * [37] David E. Roberson and Tim Seppelt.  Lasserre Hierarchy for Graph Isomorphism and Homomorphism Indistinguishability.  In Kousha Etessami, Uriel Feige, and Gabriele Puppis, editors, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023), volume 261 of Leibniz International Proceedings in Informatics (LIPIcs), pages 101:1–101:18, Dagstuhl, Germany, 2023. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.  URL: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.101, doi:10.4230/LIPIcs.ICALP.2023.101.
  * [38] Barkley Rosser.  Explicit Bounds for Some Functions of Prime Numbers.  American Journal of Mathematics, 63(1):211, January 1941.  URL: https://www.jstor.org/stable/2371291, doi:10.2307/2371291.
  * [39] Tim Seppelt.  Logical Equivalences, Homomorphism Indistinguishability, and Forbidden Minors.  In Jérôme Leroux, Sylvain Lombardy, and David Peleg, editors, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023), volume 272 of Leibniz International Proceedings in Informatics (LIPIcs), pages 82:1–82:15, Dagstuhl, Germany, 2023. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.  URL: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.82, doi:10.4230/LIPIcs.MFCS.2023.82.
  * [40] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka.  How Powerful are Graph Neural Networks?  In International Conference on Learning Representations, 2019\.  URL: https://openreview.net/forum?id=ryGs6iA5Km.