theoremTheorem[section] propositionProposition[section]
lemma[proposition]Lemma corollary[proposition]Corollary remarkRemark[section]
definitionDefinition[section] observationObservation deductionDeduction Rule

# Detection of Common Subtrees
with Identical Label Distribution

Romain Azaïs
<EMAIL_ADDRESS>Florian Ingels
<EMAIL_ADDRESS>
(Inria team MOSAIC, Lyon, France)

Abstract

Frequent pattern mining is a relevant method to analyse structured data, like
sequences, trees or graphs. It consists in identifying characteristic
substructures of a dataset. This paper deals with a new type of patterns for
tree data: common subtrees with identical label distribution. Their detection
is far from obvious since the underlying isomorphism problem is graph
isomorphism complete. An elaborated search algorithm is developed and analysed
from both theoretical and numerical perspectives. Based on this, the
enumeration of patterns is performed through a new lossless compression scheme
for trees, called DAG-RW, whose complexity is investigated as well. The method
shows very good properties, both in terms of computation times and analysis of
real datasets from the literature. Compared to other substructures like
topological subtrees and labelled subtrees for which the isomorphism problem
is linear, the patterns found provide a more parsimonious representation of
the data.

Keywords: unordered trees; marked tree isomorphism; DAG compression; frequent
pattern mining

##  1 Introduction

###  1.1 Context

Tree data are ubiquitous, especially in biology and computer science, but also
non-Euclidean [9], which prevents them from being analysed by classical
statistical methods adapted to multi-dimensional data. Therefore, they require
the development of specific tools that take into account their structured
nature. Among such techniques, frequent pattern mining [1] consists in
identifying patterns, i.e. substructures, that appear often in the data. The
more elaborate the patterns searched, the more difficult the problem is: the
issue is to preserve a reasonable algorithmic complexity that allows the
search of a given family of patterns in a reasonable time.

Different types of patterns have been considered in the literature to analyse
tree data (see the survey [16] and the references therein) with a strong
interest in a specific family of patterns called subtrees [3, 23]. In these
two papers, only subtrees that appear more often than a given threshold are
considered. Reverse search [5] is a generic approach for enumerating frequent
patterns in a dataset that consists in (i) building an enumeration tree of
substructures, and then (ii) pruning it to keep only frequent patterns. It was
notably used in [3] for subtrees and in [15] for subforests, i.e. sets of
subtrees. Another technique is to enumerate all the substructures, then
evaluate their frequency. For subtrees, this can be done with DAG compression
[20], a tree compression scheme that eliminates subtree redundancies.
Interestingly, the subtree kernel (a similarity function based on comparison
of subtrees) can be evaluated from the enumeration of all the subtrees
obtained from the DAG compression of the dataset [7], showing incidentally
that this is a credible alternative to reverse search when the number of
substructures is linear.

Subtrees can be considered with or without their labels. Considering the
labels, the condition of subtree redundancy is more stringent and one may not
find frequent patterns that characterise the data. When labels are ignored,
the condition is more flexible but some information is lost. In this paper, we
propose to fill the gap between labelled and unlabelled subtrees by
considering a new type of patterns: subtrees with identical label
distribution. The frequent pattern mining algorithm that we introduce and
analyse is based on a generalisation of DAG compression to these
substructures. It allows the detection of richer patterns than labelled
subtrees while preserving the information of the labels unlike unlabelled
subtrees.

###  1.2 Background

A (rooted) tree is a connected directed graph with no undirected cycle and
such that there exists a special node called the root, which has no parent,
and such that any node different from the root has exactly one parent. In the
setting of this paper, each node $u$ of a tree $T$ carries a label, denoted by
$\overline{u}$, the nature of which is not assumed. The set of labels of $T$,
also called alphabet, is defined as
$\operatorname{\mathcal{A}}(T)=\\{\overline{u}:u\in T\\}$. The structures of
two trees $T_{1}$ and $T_{2}$ can be compared taking into account or not their
labels.

A bijection $\operatorname{\phi}:T_{1}\to T_{2}$ is a tree isomorphism if, for
any $u,v\in T_{1}$, $u$ is a child of $v$ in $T_{1}$ if and only if
$\operatorname{\phi}(u)$ is a child of $\operatorname{\phi}(v)$ in $T_{2}$. If
in addition, for any $u\in T_{1}$,
$\overline{u}=\overline{\operatorname{\phi}(u)}$, then $\operatorname{\phi}$
is a labelled tree isomorphism.

The existence of a (labelled or not) tree isomorphism (which can be
established in linear time [2, 21]) induces an equivalence relation on the set
of trees. $T_{1}\simeq T_{2}$ means that there exists a tree isomorphism
between $T_{1}$ and $T_{2}$. Adding $l$ as a subscript to symbol $\simeq$
means that tree isomorphism is considered with labels.

Subtrees are an important class of tree substructures. A subtree $T(v)$ of a
tree $T$ is the tree made of the node $v$ and all its descendants in $T$. $T$
can have internal repetitions in its subtrees, regardless of the isomorphism
used to evaluate them. DAG compression aims at eliminating these redundancies
through the construction of a new graph
$\operatorname{\mathfrak{R}}_{\ast}(T)$ (where
$\ast\in\\{\simeq,\simeq_{l}\\}$ denotes the selected equivalence relation)
which contains each of the subtrees of $T$ only once, up to isomorphism [20].
Consequently, parsimonious enumeration of subtrees for frequent pattern mining
can be realised from the graph $\operatorname{\mathfrak{R}}_{\ast}(T)$.

The set of vertices of $\operatorname{\mathfrak{R}}_{\ast}(T)$ corresponds to
the set of equivalence classes of the subtrees of $T$. Let
$s:\operatorname{\mathfrak{R}}_{\ast}(T)\to T$ be a section, i.e. an injective
function such that the equivalence class of $s(a)$ is $a$. If we consider
labelled tree isomorphisms, each node $a$ of
$\operatorname{\mathfrak{R}}_{\simeq_{l}}(T)$ carries the label of $s(a)$. The
set of edges of $\operatorname{\mathfrak{R}}_{\ast}(T)$ is built as follows.
For any nodes $a$ and $b$ in $\operatorname{\mathfrak{R}}_{\ast}(T)$, there
are as many edges from $a$ to $b$ as the number of apparitions (up to
isomorphism) of $s(b)$ as a child of $s(a)$. The graph
$\operatorname{\mathfrak{R}}_{\ast}(T)$ can be computed in linear time [20].
It is a DAG that compresses lossless the structure of $T$. Lossless means that
a tree in the same equivalence class (with respect to the selected equivalence
relation $\ast$) as $T$ can be reconstructed. However, it should be noted that
labels of $T$ can not be inferred when working with unlabelled tree
isomorphisms: the DAG $\operatorname{\mathfrak{R}}_{\simeq}(T)$ does not carry
any piece of information about them. Figure 1 illustrates DAG compression on
an example for both $\simeq$ and $\simeq_{l}$.

$0$$1$$2$$2$$4$$3$$4$$8$$6$$3$$4$$9$$16$$3$$4$$6$$8$$18$$32$$6$$8$$T$$\operatorname{\mathfrak{R}}_{\simeq}(T)$$0$$1$$2$$2$$4$$3$$4$$8$$6$$3$$4$$9$$16$$6$$8$$18$$32$$\operatorname{\mathfrak{R}}_{\simeq_{l}}(T)$
Figure 1: From left to right: a labelled tree $T$, its unlabelled DAG
compression $\operatorname{\mathfrak{R}}_{\simeq}(T)$ and its labelled DAG
compression $\operatorname{\mathfrak{R}}_{\simeq_{l}}(T)$. Nodes with same
equivalence class (with respect to $\simeq$) are colored accordingly.

By definition, equivalence relation $\simeq_{l}$ is more stringent than
$\simeq$, i.e. $T_{1}\simeq_{l}T_{2}\,\Rightarrow\,T_{1}\simeq T_{2}$. This
means that patterns detected for $\simeq$ are more frequent and can help to
detect more similarities in the data, but without taking into account the
labels. This is also reflected in compression levels, because, for any tree
$T$,
$\operatorname{\mathfrak{R}}_{\simeq}(T)\subset\operatorname{\mathfrak{R}}_{\simeq_{l}}(T)$.
Nevertheless, $\operatorname{\mathfrak{R}}_{\simeq}(T)$ loses the piece of
information carried by the labels of $T$.

A tree isomorphism $\operatorname{\phi}$ between two trees $T_{1}$ and $T_{2}$
naturally induces a binary relation $\mathrel{R_{\operatorname{\phi}}}$ over
$\operatorname{\mathcal{A}}(T_{1})\times\operatorname{\mathcal{A}}(T_{2})$,
defined as, for any $x\in\operatorname{\mathcal{A}}(T_{1})$ and
$y\in\operatorname{\mathcal{A}}(T_{2})$,

$x\mathrel{R_{\operatorname{\phi}}}y\quad\iff\quad\exists\,u\in
T_{1},~{}(x=\overline{u})\wedge(y=\overline{\operatorname{\phi}(u)}).$

Such a relation $\mathrel{R_{\operatorname{\phi}}}$ is said to be a bijection
if and only if, for any $x\in\operatorname{\mathcal{A}}(T_{1})$, there exists
a unique $y\in\operatorname{\mathcal{A}}(T_{2})$, which we denote
$f_{\operatorname{\phi}}(x)$, so that $x\mathrel{R_{\operatorname{\phi}}}y$,
and conversely if, for any $y\in\operatorname{\mathcal{A}}(T_{2})$, there
exists a unique $x\in\operatorname{\mathcal{A}}(T_{1})$ so that
$x\mathrel{R_{\operatorname{\phi}}}y$.

A tree isomorphism $\operatorname{\phi}$ is said to be a tree ciphering if and
only if $\mathrel{R_{\operatorname{\phi}}}$ is a bijection. The bijective
function
$f_{\operatorname{\phi}}:\operatorname{\mathcal{A}}(T_{1})\to\operatorname{\mathcal{A}}(T_{2})$
is called a cipher.

An example of tree ciphering is shown in Figure 2.

$1$$2$$2$$4$$3$$4$$8$$6$$3$$4$$9$$16$$3$$4$$6$$8$$18$$32$$6$$8$$T_{1}$$T_{2}$$\operatorname{\phi}$

$1$$2$$3$$4$$9$$16$$2$$4$$6$$8$$18$$32$$f_{\operatorname{\phi}}$

Figure 2: Two topologically isomorphic labelled trees $T_{1}$ and $T_{2}$, as
well as an example of tree isomorphism $\operatorname{\phi}$ between them
(left). $\operatorname{\phi}$ is also a tree ciphering, as the binary relation
$R_{\operatorname{\phi}}$ is bijective and induces a cipher
$f_{\operatorname{\phi}}$ (right). Nodes and mapping $\operatorname{\phi}$ are
colored according to the corresponding relations between labels in
$f_{\operatorname{\phi}}$. Note that $\operatorname{\phi}$ is not the only
tree isomorphism that yields a tree ciphering for these particular trees.

The existence of a tree ciphering isomorphism induces an equivalence relation
on the set of trees [14] which we denote $\sim$. By definition, relation
$\sim$ is more stringent than $\simeq$ but also less stringent than
$\simeq_{l}$, i.e

$T_{1}\simeq_{l}T_{2}\,\Rightarrow\,T_{1}\sim T_{2}\,\Rightarrow\,T_{1}\simeq
T_{2}.$ (1)

###  1.3 Objectives of the paper

As aforementioned, $\simeq_{l}$ is less flexible than $\simeq$ which implies
that corresponding patterns are less frequent and can miss some forms of
similarity. However, $\simeq_{l}$ keeps the piece of information carried by
the labels. In light of (1), equivalence relation $\sim$ is somewhere in-
between making related patterns, i.e. subtrees with identical label
distribution, of great interest for tree data analysis. If it exists, the
compression scheme $\operatorname{\mathfrak{R}}_{\sim}$ based on $\sim$ should
be a good solution for parsimonious enumeration of such patterns, and
therefore for frequent pattern mining. In addition, it should achieve a better
compression level than $\operatorname{\mathfrak{R}}_{\simeq_{l}}$ while
preserving the labels contrary to $\operatorname{\mathfrak{R}}_{\simeq}$.

However, before addressing the issue of compression, it is important to note
that the tree ciphering isomorphism problem (which consists in determining if
a tree ciphering exists between two trees) itself is far from trivial:
referred to as marked tree isomorphism problem, it is graph isomorphism
complete [10], i.e. as difficult as the graph isomorphism problem, to which no
polynomial algorithm nor proof of NP-completeness is known [19], although a
quasi-polynomial algorithm was recently exhibited [8].

In addition, one can already expect from $\operatorname{\mathfrak{R}}_{\sim}$
a more complex conceptual definition than for
$\operatorname{\mathfrak{R}}_{\simeq_{l}}$ and
$\operatorname{\mathfrak{R}}_{\simeq}$. Indeed, the ciphers involved in the
tree ciphering isomorphisms will have to be transferred to the compression
version to allow the lossless reconstruction of the tree and its labels.
However, ciphers correspond to pairwise comparisons of subtrees, for which
there is no equivalent in DAG compressions
$\operatorname{\mathfrak{R}}_{\simeq_{l}}$ and
$\operatorname{\mathfrak{R}}_{\simeq}$. In particular, there is not a single
cipher per equivalence class contrary to labels in
$\operatorname{\mathfrak{R}}_{\simeq_{l}}$.

This paper aims to develop DAG-RW compression, a new compression scheme that
generalises DAG compression to the equivalence relation $\sim$ (RW stands for
rewritable to indicate that the labels are evaluated through a cipher) as an
algorithmic solution for detection of frequent subtrees with identical pattern
distribution. For this purpose, we address the following points.

#### Algorithm for tree ciphering isomorphism

If one wants to establish a compression method based on tree ciphering
isomorphism, one must be able to quickly compute the corresponding equivalence
classes, and this while the problem is graph isomorphism complete.

The reduction from a marked tree to a graph being linear [10], we could
consider using graph isomorphism resolution methods rather than algorithms
built to directly deal with marked trees. Even if there exist graph
isomorphism algorithms that are very efficient in practice [18], the majority
of them do not construct an isomorphism (while they are required in our
approach), but seek to compute a certificate of non-isomorphism, often based
on vertex invariants. For example, in Weisfeiler-Lehman algorithms, also known
as color refinement algorithms [22], graphs are colored according to some
rules, and the color histograms are compared afterwards: if they diverge, the
graphs are not isomorphic. However, the test is incomplete in the sense that
there exist non-isomorphic graphs that share the same coloring. The
distinguishability of those algorithms is constantly improved [13] but does
not yet answer the problem for any graph. Interestingly, the histograms can be
used as the initial partition of vertices of a backtracking procedure that
aims to exhibit an isomorphism, as in [12, 3.3 Solving the isomorphism problem
directly]: the invariants reduce the number of candidates that can be mapped
with a given vertex.

> It turns out that many isomorphism problems can be directly solved in less
> time than it takes to calculate the more powerful invariants (…). — Scott
> Fortin [12, 3.2 Vertex invariants]

In the present paper, we take this piece of advice on board and propose an
efficient search algorithm to solve the tree ciphering isomorphism problem
directly from the objects of interest (which also has the benefit of avoiding
the reduction from marked trees to graphs): given two trees $T_{1}$ and
$T_{2}$, it explores the huge space of tree isomorphisms between $T_{1}$ and
$T_{2}$ and checks if they induce a tree ciphering or not. The algorithm
processes in two main steps, both based on invariants developed specifically
for marked trees: first, a search space reduction (which relies on previous
work [14]) is performed using the relations between tree cipherings and
ciphers; second, the remaining search space is explored using a sophisticated
backtracking strategy.

#### DAG-RW compression

We define the original concept of DAG-RW compression, which is lossless with
respect to both the topology and the labels, and theoretically achieves better
compression rates than conventional DAG compression with labels. Furthermore,
we use the aforementioned search algorithm for tree ciphering isomorphism to
propose a compression algorithm, which we also analyse the time-complexity.
Our compression method does not depend on this specific answer to the tree
ciphering isomorphism problem but requires the computation of a tree ciphering
and related cipher when subtrees are isomorphic, which drastically limits the
contributions on graph isomorphism available in the literature and argues for
the development of a new approach.

#### Real data analysis

On top of this, we illustrate on two real datasets that DAG-RW compression can
be used to detect frequent common subtrees with identical label distribution.
We compare the results with labelled and unlabelled subtrees and show that
this new type of patterns is relevant because it captures new forms of
similarity, making DAG-RW compression a serious candidate to perform
parsimonious analysis of tree data.

The paper is organised as follows. Forthcoming Subsection 1.4 sums up the
notation and vocabulary used in the rest of the article. Our algorithm for
tree ciphering isomorphism is investigated in Section 2. Section 3 is devoted
to DAG-RW compression: concept, algorithm, and application to frequent pattern
mining on two datasets of reference. Appendixes A and B present technical
details and proofs related to the algorithm for tree ciphering isomorphism.
All the methods and algorithms developed in this paper were implemented in the
Python library treex [6], which was used in the numerical sections of the
paper.

###  1.4 Notation and vocabulary

#### Labelled rooted trees

A rooted tree $T$ is a connected directed graph without undirected cycle and
such that there exists a special node $\operatorname{\text{\bf root}}(T)$,
which has no parent and such that any node $v\neq\operatorname{\text{\bf
root}}(T)$ has exactly one parent: $\operatorname{\text{\bf parent}}(v)$.
$\operatorname{\text{\bf children}}(v)$ denotes the set of nodes that share
$v$ as parent. With a slight abuse of notation, “$v$ is a node of $T$” is
denoted $v\in T$. $\operatorname{\text{\bf leaves}}(T)$ is the set of nodes of
$T$ without any children. $T(v)$ is the subtree of $T$ formed by $v$ and all
its descendants in $T$. Finally, each node $v$ of $T$ carries a label
$\overline{v}$, whose set, called alphabet, is denoted
$\operatorname{\mathcal{A}}(T)$, i.e.
$\operatorname{\mathcal{A}}(T)=\\{\overline{v}\,:\,v\in T\\}$.

#### Isomorphisms

Let $T_{1}$ and $T_{2}$ be two labelled rooted trees. The paper considers
three types of tree isomorphisms: unlabelled and labelled tree isomorphisms
given in Definition 1.2 and tree ciphering given in Definition 1.2.

  * •

$T_{1}\simeq T_{2}$: there exists an unlabelled tree isomorphism between
$T_{1}$ and $T_{2}$, which means that they share the same topology without any
information about their labels.

  * •

$T_{1}\sim T_{2}$: there exists a tree ciphering $\operatorname{\phi}$ from
$T_{1}$ into $T_{2}$, meaning that they share the same topology and the same
labels up to a cipher $f_{\operatorname{\phi}}$, i.e.
$\overline{\operatorname{\phi}(u)}=f_{\operatorname{\phi}}(\overline{u})$ for
any $u\in T_{1}$.

  * •

$T_{1}\simeq_{l}T_{2}$: there exists a labelled tree isomorphism
$\operatorname{\phi}$ from $T_{1}$ into $T_{2}$, meaning that they share the
same topology and the same labels, i.e.
$\overline{\operatorname{\phi}(u)}=\overline{u}$, for any $u\in T_{1}$.

The inclusion relation between these isomorphisms is given in (1). Related
equivalence classes are denoted $[T]_{\ast}$,
$\ast\in\\{\simeq,\sim,\simeq_{l}\\}$. When there is no ambiguity on the
underlying tree $T$, equivalence classes of subtrees of $T$ are noted in short
$[u]_{\ast}$ instead of $[T(u)]_{\ast}$.

#### Compression

$\operatorname{\mathfrak{R}}_{\ast}(T)$ denotes the DAG compression of the
tree $T$, which is described in Subsection 1.2 for
$\ast\in\\{\simeq,\simeq_{l}\\}$ and remains to be introduced for
$\ast=\,\sim$. We recall that $\operatorname{\mathfrak{R}}_{\simeq}(T)$
compresses the topology of $T$ but loses the pieces of information carried by
the labels of $T$, while $\operatorname{\mathfrak{R}}_{\simeq_{l}}(T)$ is a
lossless compression of $T$.

#### Topological properties

The depth of a node $u$ is the length of the path from the root of $T$ to $u$,

$\operatorname{\text{\bf depth}}(u)=\left\\{\begin{array}[]{ll}0&\text{if
}u=\operatorname{\text{\bf root}}(T),\\\ \displaystyle
1+\operatorname{\text{\bf depth}}(\operatorname{\text{\bf
parent}}(u))&\text{otherwise.}\end{array}\right.$

The height $\operatorname{\text{\bf height}}(T)$ and the degree
$\operatorname{\text{\bf deg}}(T)$ of $T$ can then be defined as the maximal
depth and the maximal number of children of its nodes, i.e.

$\operatorname{\text{\bf height}}(T)=\max_{u\in T}\,\operatorname{\text{\bf
depth}}(u)\qquad\text{and}\qquad\operatorname{\text{\bf deg}}(T)=\max_{u\in
T}\,\\#\operatorname{\text{\bf children}}(u).$

##  2 Algorithm for tree ciphering isomorphism

This section presents our algorithm to find, if it exists, a tree ciphering
between two trees $T_{1}$ and $T_{2}$. Exploring tree isomorphisms, the
algorithm reduces the search space using back and forth deductions on the
topology and the labels. This part relies on and improves our previous work
[14]. Then the remaining space is explored using a backtracking strategy.

###  2.1 Incremental construction of a tree ciphering

Starting from trivial objects, the algorithm incrementally builds, if
possible, a bijection $\operatorname{\phi}$ on the nodes of the trees and a
bijection $f$ on the labels of the nodes. At any step of the algorithm:

  * •

$\operatorname{\phi}$ maps a subset of nodes of tree $T_{1}$ to a subset of
nodes of tree $T_{2}$ so that, if $u$ is a child of $v$ in $T_{1}$ and both
are in the domain of $\operatorname{\phi}$, then $\operatorname{\phi}(u)$ is a
child of $\operatorname{\phi}(v)$ in $T_{2}$;

  * •

$f$ maps a subset of labels of $\operatorname{\mathcal{A}}(T_{1})$ to a subset
of labels of $\operatorname{\mathcal{A}}(T_{2})$ so that
$f(\overline{u})=\overline{v}$ as soon as $\operatorname{\phi}(u)=v$.

If the algorithm goes until the end, i.e. if
$\operatorname{\text{dom}}(\operatorname{\phi})=T_{1}$ and
$\operatorname{\text{dom}}(f)=\operatorname{\mathcal{A}}(T_{1})$, then, in
light of Definitions 1.2 and 1.2, $\operatorname{\phi}$ and $f$ correspond to
a tree ciphering and related cipher. The incremental update of the domains of
$\operatorname{\phi}$ and $f$ is performed using the following method.

Let $\psi:A_{\psi}\to B_{\psi}$ be a bijection with $A_{\psi}\subset A$ and
$B_{\psi}\subset B$, and $(a,b)\in A\times B$. If $a\in A_{\psi}$ and
$\psi(a)=b$ or $a\notin A_{\psi}$ and $b\notin B_{\psi}$, then $\psi$ can be
extended as the bijection $\psi_{(a,b)}$ from $A_{\psi}\cup\\{a\\}$ into
$B_{\psi}\cup\\{b\\}$ as

$\psi_{(a,b)}(\alpha)=\begin{cases}\psi(\alpha)&\text{if }\alpha\in
A_{\psi},\\\ b&\text{if }\alpha=a.\end{cases}$

Algorithm 1 tests the extension condition and extends the bijection when
possible.

Input: $\psi:A_{\psi}\to B_{\psi},a\in A,b\in B$

Output: $\top$ if $\psi$ can be extended

1 if  _$a\in A_{\psi}$ and $\psi(a)=b$_ then

2 return $\top$

3 else if  _$a\notin A_{\psi}$ and $b\notin B_{\psi}$_ then

4 $\psi\leftarrow\psi_{(a,b)}$

5 return $\top$

6 else

7 return $\bot$

Algorithm 1 ExtBij

Now the question is to wisely propose elements to extend the domains of
$\operatorname{\phi}$ and $f$. We proceed in three main steps: deductions from
topology given in Subsection 2.2, deductions from labels given in Subsection
2.3, backtracking given in Subsection 2.4.

###  2.2 Deductions from topology

#### Partition of nodes into bags

We assume here that some nodes and labels have already been mapped through
$\operatorname{\phi}$ and $f$ and aim to increase their domains. To this end,
nodes of $T_{1}$ and $T_{2}$ that are not mapped via $\operatorname{\phi}$ can
be sorted into bags.

A bag $\mathbf{B}$ is a couple $(B_{1},B_{2})$, with $B_{i}\subset T_{i}$, so
that $\\#B_{1}=\\#B_{2}$, which is denoted $\\#\mathbf{B}$.

A bag $\mathbf{B}$ contains nodes of $T_{1}$ and $T_{2}$ which we know (in a
trivial way or by intricate deductions) must be mapped together to satisfy the
conditions of a tree ciphering. For instance, if $\operatorname{\phi}(u)=v$,
then $(\operatorname{\text{\bf children}}(u),\operatorname{\text{\bf
children}}(v))$ forms a bag: $\operatorname{\phi}$ can not be a tree
isomorphism if a child of $u$ is not mapped with a child of $v$. Another
elementary bag is $(\operatorname{\text{\bf
leaves}}(T_{1}),\operatorname{\text{\bf leaves}}(T_{2}))$. At this point, we
assume that the nodes of $T_{1}$ and $T_{2}$ not mapped via
$\operatorname{\phi}$ are sorted into bags, which set is denoted
$\operatorname{\mathbb{B}}$. The number of possible completions of
$\operatorname{\phi}$ is therefore given by

$N(\operatorname{\mathbb{B}})=\prod_{\mathbf{B}\in\operatorname{\mathbb{B}}}\\#\mathbf{B}!,$
(2)

which evaluates the size of the remaining search space.

If a bag $\mathbf{B}$ is of size $1$, i.e. $\mathbf{B}=(u,v)\in T_{1}\times
T_{2}$, then one can call Algorithm 1 to try to extend $\operatorname{\phi}$
and $f$ with $\operatorname{\phi}(u)=v$ and $f(\overline{u})=\overline{v}$. If
Algorithm 1 returns $\bot$, then it means $T_{1}\nsim T_{2}$. Otherwise, the
domains of $\operatorname{\phi}$ and $f$ can be extended and this new piece of
information can be used to refine the partition of the nodes into finer bags.
The recursive improvements in bags due to such a mapping attempt are performed
by function MapNodes given in the next paragraph.

As long as there exist bags of the form $\mathbf{B}=(u,v)\in T_{1}\times
T_{2}$, call MapNodes$(u,v,\operatorname{\phi},f)$, and delete $\mathbf{B}$
from $\operatorname{\mathbb{B}}$.

#### Mapping nodes

If two nodes $u\in T_{1}$ and $v\in T_{2}$ can be mapped as
$\operatorname{\phi}(u)=v$, i.e. if
$\textsc{ExtBij}(f,\overline{u},\overline{v})$ and
$\textsc{ExtBij}(\operatorname{\phi},u,v)$ return $\top$, then (i)
$\operatorname{\phi}(\operatorname{\text{\bf
parent}}(u))=\operatorname{\text{\bf parent}}(v)$, (ii) the elements of
$\operatorname{\text{\bf children}}(u)$ must be mapped with those of
$\operatorname{\text{\bf children}}(v)$, and (iii)
$f(\overline{u})=\overline{v}$. These observations are compiled into Algorithm
2, which is used whenever nodes should be mapped together. It uses the
subroutine SplitChildren, given in Algorithm 3 and illustrated in Figure 3, to
address condition (ii), and recursively separate the children of the mapped
nodes from the other nodes with which they are partitioned. The recursive
nature of SplitChildren represents a significant improvement compared to [14,
3.3 Mapping nodes]. It should be noted that, if at any step MapNodes returns
$\bot$, then we can conclude that $T_{1}$ and $T_{2}$ are not isomorphic with
respect to $\sim$.

1

Input: $u\in T_{1},v\in T_{2},\operatorname{\phi},f$

2 if  _ExtBij $(f,\overline{u},\overline{v})$ and
ExtBij$(\operatorname{\phi},u,v)$_ then

3 SplitChildren$(\\{u\\},\\{v\\})$

4 if  _$\operatorname{\phi}(\operatorname{\text{\bf
parent}}(u))=\operatorname{\text{\bf parent}}(v)$_ then

5 return $\top$

6 else

7 return MapNodes($\operatorname{\text{\bf parent}}(u),\operatorname{\text{\bf
parent}}(v),\operatorname{\phi},f$)

8

9else

10 return $\bot$

Algorithm 2 MapNodes

Input: $S_{u},S_{v}$

1 $\mathcal{C}_{u}\leftarrow\bigcup_{w\in S_{u}}\operatorname{\text{\bf
children}}(w)$

2 $\mathcal{C}_{v}\leftarrow\bigcup_{w\in S_{v}}\operatorname{\text{\bf
children}}(w)$

3 for  _$\mathbf{B}\in\operatorname{\mathbb{B}}$_ do

4 $B_{u}\leftarrow B_{1}\cap\mathcal{C}_{u}$

5 $B_{v}\leftarrow B_{2}\cap\mathcal{C}_{v}$

6 if  _$B_{u}\neq\emptyset$ and $B_{1}\setminus B_{u}\neq\emptyset$_ then

7 Add $(B_{u},B_{v})$ and $(B_{1}\setminus B_{u},B_{2}\setminus B_{v})$ to
$\operatorname{\mathbb{B}}$

8 SplitChildren$(B_{u},B_{v})$

9 SplitChildren$(B_{1}\setminus B_{u},\allowbreak B_{2}\setminus B_{v})$

10 Delete $\mathbf{B}$ from $\operatorname{\mathbb{B}}$

11

Algorithm 3 SplitChildren

$u$$v$$\operatorname{\phi}$$B_{1}$$B_{2}$$B_{u}$$B_{v}$$B_{1}\setminus
B_{u}$$B_{2}\setminus B_{v}$ Figure 3: Illustration of SplitChildren. The bag
$(B_{1},B_{2})$ (above) is split into two bags after the mapping of $u$ and
$v$, one composed of the children of $u$ and $v$, and the other with the
remaining nodes (below). Recursively, the bags of their descendants are also
split.

#### Reduction of search space

To determine whether $T_{1}\sim T_{2}$, it is required that $T_{1}\simeq
T_{2}$, which we can check in linear time [2, Theorem 3.3] together with
assigning to the subtrees of $T_{1}$ and $T_{2}$ their equivalence class. The
following steps are then taken in order. They will be illustrated on a
followed example, beginning with Figure 4. In addition, Appendix A indicates
how each of the manipulations of the system theoretically reduces the size of
the search space.

A. Histogram of labels. We first proceed to a verification (computable in
linear time) which allows to eliminate some obvious cases where $T_{1}\nsim
T_{2}$. In a traversal of $T_{i}$, we can count the number $N_{i}(a)$ of
occurrences of each label $a\in\operatorname{\mathcal{A}}(T_{i})$. Then we
consider
$H_{i}:n\in\mathbb{N}\mapsto\\{a\in\operatorname{\mathcal{A}}(T_{i}):N_{i}(a)=n\\}$,
which represents the histogram of labels of $T_{i}$. If the two histograms do
not coincide, i.e. if there exists $n\in\mathbb{N}$ such that
$\\#H_{1}(n)\neq\\#H_{2}(n)$, then we can conclude (in linear time) that
$T_{1}\nsim T_{2}$. Otherwise, $\operatorname{\text{supp}}(H)$ denotes the
support of the histograms,

$\operatorname{\text{supp}}(H)=\left\\{n\in\mathbb{N}~{}:~{}\\#H_{1}(n)=\\#H_{2}(n)>0\right\\}.$

We initialise the different parameters of the algorithm as follows:
$\operatorname{\text{dom}}(\operatorname{\phi})=\operatorname{\text{dom}}(f)=\emptyset$
and all the nodes of $T_{1}$ and $T_{2}$ have to be sorted into bags, for
which we work from the histograms of labels. Since it is not possible to map
nodes whose labels do not have the same number of occurrences in their
respective tree, the set $\operatorname{\mathbb{B}}$ is formed of bags
$\mathbf{B}(n)$, $n\in\operatorname{\text{supp}}(H)$, such that

$B_{i}(n)=\\{u\in T_{i}~{}:~{}\overline{u}\in H_{i}(n)\\}.$

See Figure 4 for an example. It should be noted that, in the case where all
labels appear the same number of times each, we would then have a single bag
containing all the nodes.

$B$$u_{1}$$B$$u_{2}$$A$$u_{3}$$A$$u_{4}$$B$$u_{5}$$A$$u_{6}$$A$$u_{7}$$B$$u_{8}$$C$$u_{9}$$C$$u_{10}$$C$$u_{11}$$D$$u_{12}$$E$$u_{13}$$D$$u_{14}$$E$$u_{15}$$C$$u_{16}$$T_{1}$$\beta$$v_{1}$$\beta$$v_{2}$$\alpha$$v_{3}$$\alpha$$v_{4}$$\alpha$$v_{5}$$\beta$$v_{6}$$\gamma$$v_{7}$$\gamma$$v_{8}$$\beta$$v_{9}$$\alpha$$v_{10}$$\gamma$$v_{11}$$\delta$$v_{12}$$\eta$$v_{13}$$\eta$$v_{14}$$\delta$$v_{15}$$\gamma$$v_{16}$$T_{2}$
Figure 4: Running example: histogram of labels (step 1/6). Two topologically
isomorphic labelled trees $T_{1}$ (left) and $T_{2}$ (right). The color on
nodes indicates the equivalence class under $\simeq$. The nodes have been
numbered from $u_{1}$ to $u_{16}$ in $T_{1}$ (resp. from $v_{1}$ to $v_{16}$
in $T_{2}$) in breadth-first search order. The histograms of labels give
$H_{1}(2)=\\{D,E\\}$, $H_{1}(4)=\\{A,B,C\\}$ and $H_{2}(2)=\\{\delta,\eta\\}$,
$H_{2}(4)=\\{\alpha,\beta,\gamma\\}$. Since the histograms coincide, we
initialise the bags (gray boxes) by grouping together the nodes whose labels
appear with the same frequency. The initial size of the search space is
$N(\operatorname{\mathbb{B}})=12!\times 4!=11,496,038,400$.

B. Depth. We distinguish nodes according to their depth: two mapped nodes must
be at the same depth. For any
$\mathbf{B}=(B_{1},B_{2})\in\operatorname{\mathbb{B}}$, we create the new bags
$\mathbf{B}(d)$, $d\in[\\![0,\operatorname{\text{\bf height}}(T_{i})]\\!]$,
such that $B_{i}(d)=\\{u\in B_{i}:\operatorname{\text{\bf depth}}(u)=d\\}$,
then we remove $\mathbf{B}$ from $\operatorname{\mathbb{B}}$. After this
operation, we apply Deduction Rule 2.2. Since the roots are the only nodes of
depth zero, the rule will at least apply to their bag and they will be mapped
together. See Figure 5 for an example.

$B$$u_{1}$$B$$u_{2}$$A$$u_{3}$$A$$u_{4}$$B$$u_{5}$$A$$u_{6}$$A$$u_{7}$$B$$u_{8}$$C$$u_{9}$$C$$u_{10}$$C$$u_{11}$$D$$u_{12}$$E$$u_{13}$$D$$u_{14}$$E$$u_{15}$$C$$u_{16}$$T_{1}$$\beta$$v_{1}$$\beta$$v_{2}$$\alpha$$v_{3}$$\alpha$$v_{4}$$\alpha$$v_{5}$$\beta$$v_{6}$$\gamma$$v_{7}$$\gamma$$v_{8}$$\beta$$v_{9}$$\alpha$$v_{10}$$\gamma$$v_{11}$$\delta$$v_{12}$$\eta$$v_{13}$$\eta$$v_{14}$$\delta$$v_{15}$$\gamma$$v_{16}$$T_{2}$
Figure 5: Running example: depth (step 2/6). Since $u_{1}$ and $v_{1}$ are the
only nodes with depth zero, via Deduction Rule 2.2, we map
$\operatorname{\phi}(u_{1})=v_{1}$ and $f(B)=\beta$. The children of $u_{1}$
and $v_{1}$ should be set aside from the other nodes according to the
SplitChildren procedure, but they are already alone in their bag. The size of
the search space is now $N(\operatorname{\mathbb{B}})=5!\times 6!\times
4!=2,073,600$.

C. Equivalence class. We distinguish nodes according to their equivalence
class (with respect to $\simeq$): two mapped nodes must be the roots of
isomorphic subtrees. For any
$\mathbf{B}=(B_{1},B_{2})\in\operatorname{\mathbb{B}}$, we define
$B_{i}(c)=\\{u\in B_{i}:[u]_{\simeq}=c\\}$. We add a new bag
$(B_{1}(c),B_{2}(c))$ to $\operatorname{\mathbb{B}}$ for each such $c$, and
remove $\mathbf{B}$ from $\operatorname{\mathbb{B}}$. Once all bags have been
partitioned, we apply Deduction Rule 2.2. See Figure 6 for an example.

$B$$u_{1}$$B$$u_{2}$$A$$u_{3}$$A$$u_{4}$$B$$u_{5}$$A$$u_{6}$$A$$u_{7}$$B$$u_{8}$$C$$u_{9}$$C$$u_{10}$$C$$u_{11}$$D$$u_{12}$$E$$u_{13}$$D$$u_{14}$$E$$u_{15}$$C$$u_{16}$$T_{1}$$\beta$$v_{1}$$\beta$$v_{2}$$\alpha$$v_{3}$$\alpha$$v_{4}$$\alpha$$v_{5}$$\beta$$v_{6}$$\gamma$$v_{7}$$\gamma$$v_{8}$$\beta$$v_{9}$$\alpha$$v_{10}$$\gamma$$v_{11}$$\delta$$v_{12}$$\eta$$v_{13}$$\eta$$v_{14}$$\delta$$v_{15}$$\gamma$$v_{16}$$T_{2}$
Figure 6: Running example: equivalence class (step 3/6). Since $u_{2}$ and
$v_{2}$ are the only nodes with class  and depth 1, via Deduction Rule 2.2, we
map $\operatorname{\phi}(u_{2})=v_{2}$ (we already have $f(B)=\beta$). Also,
since $u_{2}$ and $v_{2}$ have no children and their parents are already
mapped together, the process stops. The size of the search space is now
$N(\operatorname{\mathbb{B}})=(2!)^{2}\times 6!\times 4!=69,120$.

D. Parents. If two nodes are mapped together, so are the parents. We inspect
each bag $\mathbf{B}=(B_{1},B_{2})$ by increasing depth and replace it by the
new bags $\mathbf{B}(s)$,
$s\in\operatorname{\mathbb{B}}\setminus\\{\mathbf{B}\\}$, such that
$B_{i}(s)=\\{u\in B_{i}:\operatorname{\text{\bf parent}}(u)\in s\\}$. Visiting
the bags by increasing depth ensures that we have subdivided the bags
containing the parents before turning to the children. Once all bags have been
partitioned, we apply Deduction Rule 2.2. See Figure 7 for an example.

$B$$u_{1}$$B$$u_{2}$$A$$u_{3}$$A$$u_{4}$$B$$u_{5}$$A$$u_{6}$$A$$u_{7}$$B$$u_{8}$$C$$u_{9}$$C$$u_{10}$$C$$u_{11}$$D$$u_{12}$$E$$u_{13}$$D$$u_{14}$$E$$u_{15}$$C$$u_{16}$$T_{1}$$\beta$$v_{1}$$\beta$$v_{2}$$\alpha$$v_{3}$$\alpha$$v_{4}$$\alpha$$v_{5}$$\beta$$v_{6}$$\gamma$$v_{7}$$\gamma$$v_{8}$$\beta$$v_{9}$$\alpha$$v_{10}$$\gamma$$v_{11}$$\delta$$v_{12}$$\eta$$v_{13}$$\eta$$v_{14}$$\delta$$v_{15}$$\gamma$$v_{16}$$T_{2}$
Figure 7: Running example: parents (step 4/6). The only modification happens
when looking at nodes of depth 2: the bag
$(\\{u_{7},u_{8},u_{9},u_{10},u_{11},u_{16}\\},\\{v_{7},v_{8},v_{9},v_{10},v_{11},v_{16}\\})$
is split according to the bags of the parents
$(\\{u_{3},u_{4}\\},\\{v_{3},v_{4}\\})$ and
$(\\{u_{5},u_{6}\\},\\{v_{5},v_{6}\\})$. The size of the search space is now
$N(\operatorname{\mathbb{B}})=(2!)^{3}\times(4!)^{2}=4,608$.

###  2.3 Deductions from labels

#### From bags to collections

The initialisation and the first four steps of the algorithm given in
Subsection 2.2 only rely on topological properties. Now we use the labels to
process the remaining bags: denoting $B_{i}(a)=\\{u\in
B_{i}\,:\,\overline{u}=a\\}$, each bag $\mathbf{B}$ is replaced by

$\mathbf{C}=\left(\left\\{B_{1}(a)~{}:~{}a\in\\{\overline{u}\,:\,u\in
B_{1}\\}\right\\}~{},~{}\\{B_{2}(a)~{}:~{}a\in\\{\overline{u}\,:\,u\in
B_{2}\\}\right),$

which we call a collection.

A collection $\mathbf{C}$ is a couple $(C_{1},C_{2})$, with $C_{i}\subset
2^{T_{i}}$, so that:

  * •

for any $P\in C_{i}$, all the nodes of $P$ share the same label, which is
denoted $\overline{P}$;

  * •

for any $n\in\mathbb{N}$, the sets $C_{1,n}=\\{P\in C_{1}\,:\,\\#P=n\\}$ and
$C_{2,n}=\\{P\in C_{2}\,:\,\\#P=n\\}$ share the same cardinality. In that
case, $\mathbf{C}_{n}=(C_{1,n},C_{2,n})$ and $\\#\mathbf{C}_{n}=\\#C_{i,n}$.

$\operatorname{\text{supp}}(\mathbf{C})$ denotes the set of integers $n$ such
that $\\#\mathbf{C}_{n}>0$.

Collections, which set is denoted $\operatorname{\mathbb{C}}$, are composed of
sets of nodes that share the same label and are susceptible to be put together
in a bag. When converting bags into collections, if the second condition is
not satisfied, then we can conclude $T_{1}\nsim T_{2}$. On the other hand, the
first condition is necessarily true by construction. It should be noted that,
at this stage, the set $\operatorname{\mathbb{B}}$ of bags is now empty. The
transition from bags to collections is illustrated on the running example in
Figure 8.

$A$$u_{3}$$A$$u_{4}$$\alpha$$v_{3}$$\alpha$$v_{4}$$n=2$$C_{1}$$C_{2}$$\mathbf{C}$$A$$u_{7}$$B$$u_{8}$$C$$u_{9}$$C$$u_{10}$$\beta$$v_{9}$$\alpha$$v_{10}$$\gamma$$v_{7}$$\gamma$$v_{8}$$n=1$$n=2$$C^{\prime}_{1}$$C^{\prime}_{2}$$\mathbf{C^{\prime}}$$f$$A$$B$$C$$D$$E$$\alpha$$\beta$$\gamma$$\delta$$\eta$$C$$u_{11}$$C$$u_{16}$$\gamma$$v_{11}$$\gamma$$v_{16}$$n=2$$C^{\prime\prime}_{1}$$C^{\prime\prime}_{2}$$\mathbf{C^{\prime\prime}}$$D$$u_{12}$$D$$u_{14}$$E$$u_{13}$$E$$u_{15}$$\delta$$v_{12}$$\delta$$v_{15}$$\eta$$v_{13}$$\eta$$v_{14}$$n=2$$C^{\prime\prime\prime}_{1}$$C^{\prime\prime\prime}_{2}$$\mathbf{C^{\prime\prime\prime}}$$B$$u_{5}$$A$$u_{6}$$\alpha$$v_{5}$$\beta$$v_{6}$$n=1$$C^{\prime\prime\prime\prime}_{1}$$C^{\prime\prime\prime\prime}_{2}$$\mathbf{C^{\prime\prime\prime\prime}}$
Figure 8: Running example: from bags to collections (step 5/6). All the bags
visible on Figure 7 have been converted into collections (gray boxes). The
size of the search space taking collections into account, given in (3), is now
$N(\operatorname{\mathbb{B}},\operatorname{\mathbb{C}})=2!^{8}=256$.

#### Deduction rules on collections

There are three deduction rules for collections: they all deal with labels,
but one of them uses mapped labels to improve the partition of nodes, one maps
labels from considerations on cardinalities, while the last one both maps
labels and improves the partition of nodes.

Whenever we conclude that two subsets $P$ and $Q$ of a collection should form
a bag $(P,Q)$ (because their nodes should be mapped together), we know that
the related labels $\overline{P}$ and $\overline{Q}$ should also be mapped
together. Therefore, labels whose mapping is already known must be separated
from labels that are not yet mapped. More precisely, with $C_{i}(a)=\\{P\in
C_{i}:\overline{P}=a\\}$, we introduce the following deduction rule.

As long as there exist collections $\mathbf{C}$ and labels $a$ and $b$ such
that $f(a)=b$, if $C_{1}(a)\neq\emptyset$ and $C_{1}\setminus
C_{1}(a)\neq\emptyset$, replace $\mathbf{C}$ by the collections
$\left(C_{1}(a),C_{2}(b)\right)$ and $\left(C_{1}\setminus
C_{1}(a),C_{2}\setminus C_{2}(b)\right)$.

The second deduction rule is complementary to the previous one. If a
collection contains subsets of same cardinality that all share the same label
in $T_{1}$ and $T_{2}$, then those labels must be mapped together.

As long as there exist collections $\mathbf{C}$,
$n\in\operatorname{\text{supp}}(\mathbf{C})$, and labels $a$ and $b$ not
already mapped in $f$ such that, for any $P\in C_{1,n},\overline{P}=a$ and for
any $Q\in C_{2,n},\overline{Q}=b$, call ExtBij$(f,a,b)$.

The last deduction rule aims at building bags: if $\\#\mathbf{C}_{n}=1$, then
the two corresponding subsets must form a bag, and their labels must be mapped
together.

As long as there exist collections $\mathbf{C}$ and
$n\in\operatorname{\text{supp}}(\mathbf{C})$ such that $C_{1,n}=\\{P\\}$ and
$C_{2,n}=\\{Q\\}$, call ExtBij$(f,\overline{P},\overline{Q})$, add a new bag
$(P,Q)$ to $\operatorname{\mathbb{B}}$ and remove $P$ and $Q$ from
$\mathbf{C}$.

Starting from the organization of nodes in collections defined at the previous
paragraph, Deduction Rules 2.2, 2.3, 2.3 and 2.3 are recursively applied: they
are intertwined and each deduction made imposes to check again all the rules.
The process stops when no more deductions are made, except if the conditions
are fulfilled but the deduction rule can not be applied, which shows that
$T_{1}\nsim T_{2}$. Deduction rules on collections are illustrated on the
running example in Figure 9.

$B$$u_{1}$$B$$u_{2}$$A$$u_{3}$$A$$u_{4}$$B$$u_{5}$$A$$u_{6}$$A$$u_{7}$$B$$u_{8}$$C$$u_{9}$$C$$u_{10}$$C$$u_{11}$$D$$u_{12}$$E$$u_{13}$$D$$u_{14}$$E$$u_{15}$$C$$u_{16}$$T_{1}$$\beta$$v_{1}$$\beta$$v_{2}$$\alpha$$v_{3}$$\alpha$$v_{4}$$\alpha$$v_{5}$$\beta$$v_{6}$$\gamma$$v_{7}$$\gamma$$v_{8}$$\beta$$v_{9}$$\alpha$$v_{10}$$\gamma$$v_{11}$$\delta$$v_{12}$$\eta$$v_{13}$$\eta$$v_{14}$$\delta$$v_{15}$$\gamma$$v_{16}$$T_{2}$

$D$$u_{12}$$E$$u_{13}$$\eta$$v_{14}$$\delta$$v_{15}$$n=1$$C^{\ast}_{1}$$C^{\ast}_{2}$$\mathbf{C^{\ast}}$$D$$u_{14}$$E$$u_{15}$$\delta$$v_{12}$$\eta$$v_{13}$$n=1$$C^{\ast\ast}_{1}$$C^{\ast\ast}_{2}$$\mathbf{C^{\ast\ast}}$$f$$A$$B$$C$$D$$E$$\alpha$$\beta$$\gamma$$\delta$$\eta$

Figure 9: Running example: deductions on collections (step 6/6). Starting from
the collections of Figure 8, Deduction Rules 2.2, 2.3, 2.3 and 2.3 are
recursively applied. Since $f(B)=\beta$, Deduction Rule 2.3 moves nodes
$(u_{8},v_{9})$ and $(u_{5},v_{6})$ into new collections; then Deduction Rule
2.3 allows to deduce $f(A)=\alpha$ and $f(C)=\gamma$ (for instance with
collections $\mathbf{C}$ and $\mathbf{C^{\prime\prime}}$). Deduction Rule 2.3
puts every node in bags except the ones in $\mathbf{C^{\prime\prime\prime}}$.
Most of these bags are of size $1$ and therefore allow to deduce mappings via
Deduction Rule 2.2. The mapping $\operatorname{\phi}(u_{5})=v_{6}$ provokes,
via SplitChildren, collection $\mathbf{C^{\prime\prime\prime}}$ to be divided
into collections $\mathbf{C^{\ast}}$ and $\mathbf{C^{\ast\ast}}$, for which no
further deduction is possible. The size of the search space after all
deductions is
$N(\operatorname{\mathbb{B}},\operatorname{\mathbb{C}})=2!^{3}=8$.

#### Redefinition of mapping nodes

Each of the deduction rules above changes the organization of the unmapped
nodes of $T_{1}$ and $T_{2}$ in bags and collections. Consequently, MapNodes
through SplitChildren must take into account the existence of collections. To
this end, the pseudocode of Algorithm 4 is to be added after Algorithm 3 to
redefine SplitChildren. An example is presented in Figure 10.

9 for  _$\mathbf{C}\in\operatorname{\mathbb{C}}$_ do

10 for  _$n\in\operatorname{\text{supp}}(\mathbf{C})$_ do

11 Init. $\mathbf{C}^{\prime}$ and $\mathbf{C}^{\prime\prime}$ as empty
collections

12 Init. $S_{1}$ and $S^{\prime}_{1}$ as empty sets

13 for  _$P\in C_{1,n}$_ do

14 $P_{u}\leftarrow P\cap\mathcal{C}_{u}$

15 if  _$P_{u}\neq\emptyset$ and $P\setminus P_{u}\neq\emptyset$_ then

16 Add $P_{u}$ to $C^{\prime}_{1,\\#P_{u}}$

17 Add $P\setminus P_{u}$ to $C^{\prime\prime}_{1,\\#(P\setminus P_{u})}$

18 $S_{1}\leftarrow S_{1}\cup P_{u}$

19 $S^{\prime}_{1}\leftarrow S^{\prime}_{1}\cup(P\setminus P_{u})$

20 Delete $P$ from $C_{1,n}$

21

22

23 Init. $S_{2}$ and $S^{\prime}_{2}$ as empty sets

24 for  _$Q\in C_{2,n}$_ do

25 $Q_{v}\leftarrow Q\cap\mathcal{C}_{v}$

26 if  _$Q_{v}\neq\emptyset$ and $Q\setminus Q_{v}\neq\emptyset$_ then

27 Add $Q_{v}$ to $C^{\prime}_{2,\\#Q_{v}}$

28 Add $Q\setminus Q_{v}$ to $C^{\prime\prime}_{2,\\#(Q\setminus Q_{v})}$

29 $S_{2}\leftarrow S_{2}\cup Q_{v}$

30 $S^{\prime}_{2}\leftarrow S^{\prime}_{2}\cup(Q\setminus Q_{v})$

31 Delete $Q$ from $C_{2,n}$

32

33

34 Add $\mathbf{C}^{\prime}$ and $\mathbf{C}^{\prime\prime}$ to
$\operatorname{\mathbb{C}}$

35 SplitChildren$(S_{1},S_{2})$

36 SplitChildren$(S^{\prime}_{1},S^{\prime}_{2})$

37 if  _$\operatorname{\text{supp}}(\mathbf{C})=\emptyset$_ then

38 Delete $\mathbf{C}$ from $\operatorname{\mathbb{C}}$

39

Algorithm 4 SplitChildrenSequel

$n=5$$C_{1}$$C_{2}$$\mathbf{C}$$n=2$$n=3$$C^{\prime}_{1}$$C^{\prime}_{2}$$\mathbf{C^{\prime}}$$n=2$$n=3$$C^{\prime\prime}_{1}$$C^{\prime\prime}_{2}$$\mathbf{C^{\prime\prime}}$

Figure 10: Illustration of SplitChildren on collections. The collection
$\mathbf{C}$ (above) with $n=5$ is split into two collections,
$\mathbf{C^{\prime}}$ composed of the elements of $\mathcal{C}_{u}$ and
$\mathcal{C}_{v}$ (red nodes), and $\mathbf{C^{\prime\prime}}$ with the
remaining nodes (below). Recursively, the children of red nodes, first, and
the children of non-red nodes, second, will in turn be separated from the
other nodes – whether they are present in bags or collections.

Furthermore, when recursively mapping the parents of two nodes, if the latter
were present in a collection, the other nodes with which these parents share a
subset must be put together in a bag. More precisely, let $u$ and $v$ be the
parents to be mapped, $\mathbf{C}\in\operatorname{\mathbb{C}}$ and
$n\in\operatorname{\text{supp}}(\mathbf{C})$ such that $u\in P\in C_{1,n}$ and
$v\in Q\in C_{2,n}$. In addition to mapping $u$ and $v$, we must remove $P$
and $Q$ from $\mathbf{C}_{n}$ (which may lead to new deductions) and create
bag $(P\setminus\\{u\\},Q\setminus\\{v\\})$.

#### Size of the remaining search space

When the system only consists of bags, we have established in (2) the number
of possible completions of $\operatorname{\phi}$, referred to as the size of
the search space. Now that collections have been introduced, and some bags may
have been created again (via Deduction Rule 2.3), we have to evaluate the size
of the search space in terms of both $\operatorname{\mathbb{B}}$ and
$\operatorname{\mathbb{C}}$.

Each bag $\mathbf{B}\in\operatorname{\mathbb{B}}$ still provides
$\\#\mathbf{B}!$ possible mappings. For a given collection
$\mathbf{C}\in\operatorname{\mathbb{C}}$ and a given integer
$n\in\operatorname{\text{supp}}(\mathbf{C})$, there are $\\#\mathbf{C}_{n}!$
ways of forming new bags; each such bag leading to $n!$ possible mappings. The
number of possible completions of $\operatorname{\phi}$ is therefore given by

$N(\operatorname{\mathbb{B}},\operatorname{\mathbb{C}})=\prod_{\mathbf{B}\in\operatorname{\mathbb{B}}}\\#\mathbf{B}!\prod_{\mathbf{C}\in\operatorname{\mathbb{C}}}\left(\prod_{n\in\operatorname{\text{supp}}(\mathbf{C})}\\#\mathbf{C}_{n}!\times
n!^{\\#\mathbf{C}_{n}}\right).$ (3)

###  2.4 Backtracking

The purpose of the steps in Subsections 2.2 and 2.3 is to reduce the size of
the search space by making deductions about the necessary mappings required
for a tree ciphering to exist between $T_{1}$ and $T_{2}$. When no more
deductions are possible, we propose to explore the remaining possibilities by
making arbitrary mappings, which may prove unsuccessful and break the partial
tree ciphering, in which case one must backtrack and make other choices if any
remain; otherwise one can conclude that $T_{1}\nsim T_{2}$.

At this point, the system consists of nodes already mapped and the rest
distributed among bags and collections. Since arbitrary mapping choices are to
be made, the issue here is to define precisely what these choices consist of,
and in what order to consider them.

#### On the backtracking tree

The underlying structure behind a backtracking approach is an enumeration
tree, whose nodes are called states. In the best case, we simply traverse it
from the root to a leaf; in the worst case, we explore the entirety of it.
Ensuring that the tree has a minimal number of possible states is therefore of
utmost importance to guarantee the performance of the algorithm. The design of
the exploration of the remaining search space is thus motivated by the
minimization of the number of states of the related backtracking tree.

In our case, given $\operatorname{\phi}$, $\operatorname{\mathbb{B}}$ and
$\operatorname{\mathbb{C}}$, we know that there are
$N(\operatorname{\mathbb{B}},\operatorname{\mathbb{C}})$ ways to complete
$\operatorname{\phi}$. The definition of the backtracking exploration consists
in (i) mapping nodes taken from bags together, and (ii) forming bags from sets
of nodes taken from collections. No matter how these options are implemented
and sorted, the resulting backtracking tree has precisely
$N(\operatorname{\mathbb{B}},\operatorname{\mathbb{C}})$ leaves. The aim here
is to minimize the number of internal (excluding the leaves and the root)
states in the backtracking tree. Prior to any optimization of this number, we
have the following upper-bound.

Starting from initial system given by $\operatorname{\mathbb{B}}$ and
$\operatorname{\mathbb{C}}$, the number of states of any backtracking tree
aiming to complete $\operatorname{\phi}$ into a tree ciphering isomorphism is
upper-bounded by
$2(e-1)N(\operatorname{\mathbb{B}},\operatorname{\mathbb{C}})$. Proof. The
proof can be found in Appendix B. See in particular Appendix B.3.

First, this result highlights the value of the previous phase of deductions on
topology and labels, aimed at reducing the size
$N(\operatorname{\mathbb{B}},\operatorname{\mathbb{C}})$ of the search space
as much as possible. In addition, since we know that there must be exactly
$N(\operatorname{\mathbb{B}},\operatorname{\mathbb{C}})$ leaves, we see that
the number of states of any backtracking tree is linear in the quantity of
items to enumerate. In the sequel, the efforts that are made to minimize the
number of inner states aim to reduce the value of the constant in front of
$N(\operatorname{\mathbb{B}},\operatorname{\mathbb{C}})$.

#### Processing a single bag

We assume here that the system consists of only one bag
$\mathbf{B}=(B_{1},B_{2})$. There are $\\#\mathbf{B}!$ possible mappings
between the nodes of $B_{1}$ and those of $B_{2}$. In particular, for any
$u\in B_{1}$, there are $\\#\mathbf{B}$ choices for mapping $u$ to a node
$v\in B_{2}$. Process bag $\mathbf{B}$ means mapping an arbitrary couple
$(u,v)\in B_{1}\times B_{2}$ with $\textsc{ExtBij}(\operatorname{\phi},u,v)$,
which leads (if we ignore the possible deductions that can result from it) to
a new state formed of a single bag $\mathbf{B}^{\prime}$ of size
$\\#\mathbf{B}-1$ and for which we can recursively apply the same procedure
until all nodes have been mapped or an error arises. Backtracking on the
choice $(u,v)$ amounts to choosing another node $v^{\prime}\in
B_{2}\setminus\\{v\\}$ and mapping $(u,v^{\prime})$. If there is no node $v\in
B_{2}$ that can be mapped to $u$ without generating an error, then one can
conclude that $T_{1}\nsim T_{2}$.

#### Processing a single collection

Similarly, we assume that the system consists of only one collection
$\mathbf{C}$ with a single integer $n$ such that $\\#\mathbf{C}_{n}>0$. There
are $\\#\mathbf{C}_{n}!$ possible mappings between the elements of $C_{1,n}$
and those of $C_{2,n}$. For any $P\in C_{1,n}$, there are $\\#\mathbf{C}_{n}$
choices for selecting $Q\in C_{2,n}$ to create a bag $(P,Q)$. Once this bag is
created, two strategies are possible:

  1. (i)

continue to form new bags from the remaining elements in $\mathbf{C}_{n}$,
then process all these bags one by one;

  2. (ii)

process this new bag entirely (according to the previous procedure) before
forming a new bag from the remaining elements in $\mathbf{C}_{n}$.

By virtue of upcoming Proposition 2.4, we adopt the second strategy: process
collection $\mathbf{C}_{n}$ means putting together into a bag an arbitrary
couple $(P,Q)\in C_{1,n}\times C_{2,n}$. The system is then composed of a bag
and a collection. The next paragraph says how to deal with a system composed
of both elements: in consistency with the choice of the second strategy, bags
are processed first. As a consequence, the new bag $(P,Q)$ is entirely
processed before forming new bags from the rest of $\mathbf{C}_{n}$.
Backtracking on this choice amounts to choosing a different set $Q^{\prime}\in
C_{2,n}\setminus\\{Q\\}$. As for bags, if there is no $Q\in C_{2,n}$ that can
be associated to $P$ without generating an error, then $T_{1}\nsim T_{2}$.

The backtracking tree related to strategy (ii) has fewer states than the one
related to strategy (i). Proof. The proof can be found in Appendix B. See in
particular Lemma B.2.

#### Processings bags and collections

We consider the general case where there are several bags and collections to
choose from to process. Several questions arise: between bags and collections,
which to process first? Among several bags, which one to process first? Among
several collections, which one to process first? These issues are addressed in
the next theorem.

The number of states of the backtracking tree is minimal if:

  * •

bags are processed before collections;

  * •

when processing bags, the bag $\mathbf{B}$ with the smallest cardinality
$\\#\mathbf{B}$ (among all bags) is processed first;

  * •

if there are only collections left, the collections $\mathbf{C}$ with the
largest $n=\max(\operatorname{\text{supp}}(\mathbf{C}))$ (among all
collections) are processed first by increasing cardinality
$\\#\mathbf{C}_{n}$.

Proof. The proof can be found in Appendix B. See in particular Appendix B.4.

#### Algorithm

The pseudocode for the backtracking part is provided in Algorithm 5 and
implements precisely the strategy of Theorem 2.4. During the deduction steps,
if an operation went wrong, we could immediately conclude that $T_{1}\nsim
T_{2}$; here it indicates that an unfortunate choice has been made and that
another one must be tested, if any remain. The detection of these unsuccessful
cases is done in the pseudocode via the tags try and catch: $\textbf{try}~{}X$
$\textbf{catch}~{}Y$ executes $X$ and, if an error is detected, executes $Y$
instead. A number of new procedures are also introduced: SaveState,
RestoreState and NextCandidates. The first two are self-explanatory, while the
last one, presented in Algorithm 6, generates the list of possible choices for
the next step of backtracking, following what was established earlier.

1

Input:
$\operatorname{\mathbb{B}},\operatorname{\mathbb{C}},\operatorname{\phi},f$

2
$\lambda,L\leftarrow\textsc{NextCandidates}(\operatorname{\mathbb{B}},\operatorname{\mathbb{C}})$

3
$S\leftarrow\textsc{SaveState}(\operatorname{\mathbb{B}},\operatorname{\mathbb{C}},\operatorname{\phi},f)$

4 if  _$\lambda=\text{\emph{flag}}(\operatorname{\mathbb{B}})$_ then

5 for  _$(u,v)\in L$_ do

6 try  __

7 assert MapNodes$(u,v,\operatorname{\phi},f)$

8 Apply Deduction Rules 2.2 to 2.3

9 return
Backtracking$(\operatorname{\mathbb{B}},\operatorname{\mathbb{C}},\operatorname{\phi},f)$

10

11 catch

12
$\operatorname{\mathbb{B}},\operatorname{\mathbb{C}},\operatorname{\phi},f\leftarrow\textsc{RestoreState}(S)$

13

14 return $\bot$

15 else if  _$\lambda=\text{\emph{flag}}(\operatorname{\mathbb{C}})$_ then

16 for  _$(P,Q)\in L$_ do

17 try  __

18 assert ExtBij$(f,\overline{P},\overline{Q})$

19 Delete $P$ and $Q$ from their collection

20 Add $(P,Q)$ to $\operatorname{\mathbb{B}}$

21 Apply Deduction Rules 2.2 to 2.3

22 return
Backtracking$(\operatorname{\mathbb{B}},\operatorname{\mathbb{C}},\operatorname{\phi},f)$

23 catch

24
$\operatorname{\mathbb{B}},\operatorname{\mathbb{C}},\operatorname{\phi},f\leftarrow\textsc{RestoreState}(S)$

25

26 return $\bot$

27 else

28 return $\top$

Algorithm 5 Backtracking

Input: $\operatorname{\mathbb{B}},\operatorname{\mathbb{C}}$

1 if  _$\operatorname{\mathbb{B}}\neq\emptyset$_ then

2 $\lambda\leftarrow\text{flag}(\operatorname{\mathbb{B}})$

3
$\mathbf{B}\leftarrow\operatorname{\arg\min}_{\mathbf{B}\in\operatorname{\mathbb{B}}}\\#\mathbf{B}$

4 Select $u\in B_{1}$

5 $L\leftarrow\\{(u,v):v\in B_{2}\\}$

6 else if  _$\operatorname{\mathbb{C}}\neq\emptyset$_ then

7 $\lambda\leftarrow\text{flag}(\operatorname{\mathbb{C}})$

8
$A\leftarrow\operatorname{\arg\max}_{\mathbf{C}\in\operatorname{\mathbb{C}}}\max(\operatorname{\text{supp}}(\mathbf{C}))$

9 $\mathbf{C}\leftarrow\operatorname{\arg\min}_{\mathbf{C}\in
A}\\#\mathbf{C}_{\max(\operatorname{\text{supp}}(\mathbf{C}))}$

10 Select $P\in C_{1,\max(\operatorname{\text{supp}}(\mathbf{C}))}$

11 $L\leftarrow\\{(P,Q)\,:\,Q\in C_{2,n}\\}$

12 else

13 $\lambda\leftarrow\text{flag}(\emptyset)$

14 $L\leftarrow\emptyset$

15

return $\lambda,L$

Algorithm 6 NextCandidates

#### Running example: backtracking

The deduction steps end with Figure 9, then the backtracking exploration can
start. NextCandidates$(\operatorname{\mathbb{B}},\operatorname{\mathbb{C}})$
returns $\lambda=\text{flag}(\operatorname{\mathbb{B}})$ and
$L=\\{(u_{9},v_{7}),(u_{9},v_{8})\\}$. After mapping
$\operatorname{\phi}(u_{9})=v_{7}$, one can deduce
$\operatorname{\phi}(u_{10})=v_{8}$ and start the recursion, this time on
collections. All mapping choices between the remaining nodes and labels are
acceptable: the exploration of the remaining search space does not require to
backtrack.

###  2.5 Analysis of time-complexity

#### Complexity of MapNodes

The backtracking exploration has been developed together with the analysis of
the number of possible states. The time-complexity of the two parts of our
tree ciphering algorithm requires to investigate the procedure MapNodes given
in Algorithm 2. Below, we assume that the two trees of interest are
topologically isomorphic and note $T$ their topology.

The number of calls to MapNodes is:

  * •

bounded by $\\#T$ during the deduction steps (prior to backtracking);

  * •

at least $\\#T$ for the whole algorithm (deduction steps and backtracking) if
$T_{1}\sim T_{2}$.

Proof. The first item is stated in [14, Proposition 1]. In addition, if
$T_{1}\sim T_{2}$, the algorithm maps all the nodes, which requires at least
$\\#T$ calls to MapNodes.

If $T_{1}\nsim T_{2}$, the number of calls to MapNodes in the backtracking
exploration can not be compared to $\\#T$: it may be larger if the
impossibility of building a tree ciphering is detected late in the
backtracking, or smaller if it is detected early during the deduction steps.

Considering the time-complexity of ExtBij (given in Algorithm 1) as $O(1)$,
the complexity of a call to MapNodes depends only on the complexity of the
subroutine SplitChildren (concatenation of Algorithms 3 and 4), which is
provided in the next proposition. It should be recalled that, contrary to the
version presented in [14, 3.3 Mapping nodes], SplitChildren is recursive here.

The time-complexity of SplitChildren is $O(\\#T\operatorname{\text{\bf
height}}(T))$. Proof. First, we can see that Algorithms 3 (line 2) and 4 (line
9) loop over all bags and collections. Actually, only bags and collections
containing nodes of $\mathcal{C}_{u}$ and $\mathcal{C}_{v}$ are affected. If
the implementation keeps a table that maps each node to the bag or collection
where it is stored, we can restrict the loop to relevant bags and collections.

Next, note that the first time SplitChildren is called, the nodes have already
been partitioned by depth (see B. Depth in Subsection 2.2). Recursive calls on
their children visit strictly deeper nodes, and thus necessarily different
bags, which subsequently proves that the algorithm terminates. In the worst
case, each different bag and collection is visited.

Partitioning bags or collections into two elements can be done in linear time,
assuming that testing membership to $\mathcal{C}_{u}$ or $\mathcal{C}_{v}$
takes constant time, e.g. via hash tables. A bag $\mathbf{B}$ is then
partitioned in $O(\\#\mathbf{B})$ and a collection $\mathbf{C}_{n}$ in
$O(n\\#\mathbf{C}_{n})$.

The remaining question is: how many times can a bag or a collection be further
partitioned through the various recursive calls? The worst possible case is
when all recursive calls act on the same bag or collection, i.e. the children
of the considered nodes are in the same object (see Figure 11 for an example
with bags). A bag or a collection visited at recursion depth $k$ can be
successively subdivided at most $k+1$ times. Roughly bounding $k$ by
$\operatorname{\text{\bf height}}(T)$, we obtain, over all recursive calls, a
complexity of

$O\left(\Bigg{(}\displaystyle\sum_{\mathbf{B}\in\operatorname{\mathbb{B}}}\\#\mathbf{B}+\displaystyle\sum_{\mathbf{C}\in\operatorname{\mathbb{C}}}\displaystyle\sum_{n\in\operatorname{\text{supp}}(\mathbf{C})}n\\#\mathbf{C}_{n}\Bigg{)}\times(\operatorname{\text{\bf
height}}(T)+1)\right).$

Since the bags and collections are composed of the nodes of $T_{1}$ and
$T_{2}$, the left-hand term can not be greater than $\\#T$, concluding the
proof.

Figure 11: Illustration of recursive calls of SplitChildren on bags (only the
$B_{1}$ part of bags is represented) to help the proof of Proposition 2.5. The
color of nodes indicates the parent-child relationship between sets $S_{u}$
and $\mathcal{C}_{u}$ through successive calls. The starting bag is divided in
two. The middle bag is successively divided twice: one for the red recursive
call and one for the green recursive call (the orange nodes forming the
remaining nodes). Finally, the bottom bag is successively divided three times:
one for the red recursive call, one for the green recursive call, and one for
the orange recursive call (the blue node forming the remaining node).

#### Experimental overall complexity

Given the intrinsic complexity of the tree ciphering isomorphism problem [10],
the worst-case complexity of the search algorithm that we propose in this
paper is not relevant. However, a reasonable average time-complexity can be
expected. Here we explore this question from simulated data, first when the
trees are isomorphic $T_{1}\sim T_{2}$, then when they are not $T_{1}\nsim
T_{2}$.

We suspect that the proportion of different labels found in the trees plays a
major role in the complexity. Indeed, if all labels are different or if they
are all equal, the problem becomes trivial: in those cases, any tree
isomorphism is a tree ciphering. The simulation scheme therefore involves two
parameters: the size of the trees $n$ and the proportion of different labels
$1/n\leq p\leq 1$.

The tree $T_{1}$ is simulated as follows. Its topology is a random recursive
tree with $n$ nodes [24]. $N=\max(\lfloor pn\rfloor,1)$ of them are picked at
random and receive labels $1,\dots,N$; then a random label between $1$ and $N$
is assigned to each of the remaining nodes. The exact proportion of labels is
$N/n\simeq p$.

The simulation of the tree $T_{2}$ depends on the considered scenario. In
order to analyse the case $T_{1}\sim T_{2}$, $T_{2}$ is obtained by shuffling
the children of each node of $T_{1}$. To test the case $T_{1}\nsim T_{2}$,
$T_{2}$ shares the topology of $T_{1}$ but the labels are randomly shuffled.
If $T_{1}$ and $T_{2}$ are still isomorphic, the operation is repeated. This
procedure preserves the histogram of labels: the nonexistence of a tree
ciphering will not be detected at step (i) of the algorithm. It should be
noted that, if $p=1/n$ or $p=1$, it is impossible to build a tree $T_{2}$ that
is not isomorphic to $T_{1}$ by following this method.

In each of these two cases, $500$ couples of trees $(T_{1},T_{2})$ were
simulated for each pair $(n,p)$, with $n$ from $50$ to $500$ by step of $50$
and $p$ from $0.1$ to $0.9$ by step of $0.1$ (extreme values $p=1/n$ and $p=1$
are added only when $T_{1}\sim T_{2}$), which makes a total of $100\,000$
samples. The search algorithm was implemented in the Python library treex [6]
and run on a Macbook Pro laptop with 2.6 GHz Intel Core i7 processors and 32
GB of RAM. Computation times required to test if trees $T_{1}$ and $T_{2}$ are
isomorphic are presented in Figure 12.

$T_{1}\sim T_{2}$ abcdefg$p\leq 1/3$ |  abcde$1/3<p\leq 2/3$ |  abcdef$p>2/3$
---|---|---
|  |

$T_{1}\nsim T_{2}$ abcdefg$p\leq 1/3$ |  abcde$1/3<p\leq 2/3$ |  abcdef$p>2/3$
---|---|---
|  |

Figure 12: Computation time (5th quantile, median, and 95th quantile) required
to decide on the tree ciphering isomorphism problem ($T_{1}\sim T_{2}$ (top)
and $T_{1}\nsim T_{2}$ (bottom)) as a function of the tree size and the
proportion $p$ of different labels, and proportion of outliers.

In most cases, measured computation times are less than $0.3$ seconds for
$95\%$ of the data, even for trees with $500$ nodes, which appears to be very
reasonable for a problem with such a complexity. The worst-case scenario
occurs when the trees are isomorphic with a proportion of different labels
greater than $2/3$. the median computation time for a tree of size $500$ is
around $0.35$ seconds and the 95th quantile is above $0.5$ seconds, which is
still acceptable. However, the plot of the proportion of outliers shows that
some examples resist, even after $50$ times the median computation time, which
certainly corresponds to a deep backtracking search. The existence of such
examples is of course expected but, in this proportion and with this effect,
does not drastically limit the applicability of our approach, in particular to
pattern mining.

##  3 DAG-RW compression

In this section, we define DAG-RW compression of trees, a lossless compression
scheme that eliminates their internal redundancies with respect to tree
ciphering $\sim$. We also provide the related compression algorithm and
discuss its complexity. Finally, we derive a method to detect frequent common
subtrees with identical label distribution in a tree dataset and use it to
analyse real data from the literature.

###  3.1 Concept

DAG-RW compression of a labelled unordered tree $T$ consists in a multigraph
with labelled vertices and labelled edges
$\operatorname{\mathfrak{R}}_{\sim}(T)=(V,E,L_{V},L_{E})$, where $V$ is the
set of vertices, $E$ is the multiset of edges, $L_{V}$ is the label function
of vertices, and $L_{E}$ is the label function of edges.

#### Topology

We first consider the topology $G$ of $\operatorname{\mathfrak{R}}_{\sim}(T)$.
$G=(V,E)$ is the directed multigraph defined as follows.

  * •

The set of vertices $V$ is formed by the equivalence classes $[T(u)]_{\sim}$,
denoted in short $[u]_{\sim}$, $u\in T$, with respect to the relation $\sim$.

  * •

For any $(p,q)\in V^{2}$, $(p,q)$ appears in $E$ with multiplicity $k$ if
there exists $(u,v_{1},\dots,v_{k})\in T^{k+1}$ such that
$\\{v_{1},\dots,v_{k}\\}\subset\operatorname{\text{\bf children}}(u)$ and

$\displaystyle[u]_{\sim}$ $\displaystyle=p,$ $\displaystyle\forall\,1\leq
i\leq k,\quad[v_{i}]_{\sim}$ $\displaystyle=q.$

The multigraph $G$ is a DAG with a unique source $S$. Proof. By construction,
any path in $G$ makes the size of subtrees associated to visited vertices
decrease strictly, which states that $G$ is a DAG. In addition, a vertex of
$G$ without entering edge must be associated to a subtree whose root has no
parent in $T$. $T$ is the only such subtree: this proves that $G$ has a unique
source, which is associated to the whole tree $T$.

$G$ is a lossless compression of the topology of $T$, i.e. $[T]_{\simeq}$ can
be reconstructed from $G$. Proof. One sorts the children of
$\operatorname{\text{\bf root}}(T)$ by their equivalence class (with respect
to tree ciphering): $n_{i}$ children of $\operatorname{\text{\bf root}}(T)$
are of class $p_{i}$ and $v_{i}$ denotes one of these children. By definition,
$\operatorname{\mathfrak{R}}_{\sim}(T)$ has $n_{i}$ edges from its source $S$
to $p_{i}$. Furthermore, the multigraph made of $p_{i}$ and all its
descendants in $G$ is $\operatorname{\mathfrak{R}}_{\sim}(T(v_{i}))$.
Consequently, by induction on the height of $T$, if the topology of $T(v_{i})$
can be reconstructed from $\operatorname{\mathfrak{R}}_{\sim}(T(v_{i}))$, then
the topology of $T$ can be obtained from
$\operatorname{\mathfrak{R}}_{\sim}(T)$. Initialisation of induction at height
$0$ is trivial, which states the result.

#### Selection of a section

At this stage of the definition of $\operatorname{\mathfrak{R}}_{\sim}(T)$,
there is no conceptual difference with DAG compression of trees based on
equivalence relations $\simeq_{l}$ and $\simeq$, as given in Subsection 1.2.
Indeed, the set of vertices is the set of equivalence classes of subtrees of
$T$ with respect to the considered equivalence relation, and the edges reflect
the connection between them in $T$. However, unlike conventional DAG
compression, $\operatorname{\mathfrak{R}}_{\sim}(T)$ needs to take into
account labels of $T$ up to a cipher, which requires to select a specific
section.

There exists a section $s:V\to T$ such that, for any $q\in V$,

$\exists\,p\in V,~{}(p,q)\in E~{}\Rightarrow~{}s(q)\in\operatorname{\text{\bf
children}}(s(p)).$

In the rest of the paper, $s$ denotes such a section. Proof. The section $s$
recursively built top-down by $s(S)=\operatorname{\text{\bf root}}(T)$ and, if
$s(p)=u$ then, for any $q\in V$ such that $(p,q)\in E$, $s(q)$ is selected
among the set $\\{v\in\operatorname{\text{\bf
children}}(u)\,:\,[v]_{\sim}=q\\}$, obeys the imposed conditions.

As aforementioned, the multiplicity of edge $(p,q)$ in $E$ is related to nodes
$v$ of class $q$ that share the same parent of class $p$. Now the section has
been fixed, a natural candidate to be such a parent is $s(p)$. As a
consequence, an edge of $G$ can be identified with the triplet $(p,q,v)$ where
$v\in\operatorname{\text{\bf children}}(s(p))$ such that $[v]_{\sim}=q$.

#### Labels

Labels of vertices of $G$ are defined through $s$: for any $q\in V$,
$L_{V}(q)=\overline{s(q)}$. Edge $(p,q,v)$ carries the cipher
$f_{\operatorname{\phi}}$ related to the tree ciphering $\operatorname{\phi}$
from $T(s(q))$ to $T(v)$ (which exists because $[v]_{\sim}=q$):
$L_{E}(p,q,v)=f_{\operatorname{\phi}}$. $G$ augmented with labels on its
vertices and on its edges defines $\operatorname{\mathfrak{R}}_{\sim}(T)$.

  1. (i)

For any $q\neq S$, there exists an edge $(p,q,v)\in E$ such that
$L_{E}(p,q,v)=\operatorname{\text{\bf id}}$.

  2. (ii)

Ciphers can be composed along paths of
$\operatorname{\mathfrak{R}}_{\sim}(T)$.

Proof. (i) By definition of $s$, there exists an edge $(p,q,v)$ such that
$s(q)\in\operatorname{\text{\bf children}}(s(p))$. If one selects $v=s(q)$
(which is correct because $[s(q)]_{\sim}=q$), then the cipher carried by
$(p,q,v)$ is related to the trivial isomorphism between $T(s(q))$ and itself:
$L_{E}(p,q,v)=\operatorname{\text{\bf id}}$. (ii) $\\{(p,q,v),(q,r,w)\\}$
denotes a path of length $2$ of $\operatorname{\mathfrak{R}}_{\sim}(T)$. By
definition,

$\displaystyle L_{E}(p,q,v)$
$\displaystyle:\operatorname{\mathcal{A}}(T(s(q)))\to\operatorname{\mathcal{A}}(T(v))$
$\displaystyle L_{E}(q,r,w)$
$\displaystyle:\operatorname{\mathcal{A}}(T(s(r)))\to\operatorname{\mathcal{A}}(T(w))$

But $w\in\operatorname{\text{\bf children}}(s(q))$, which implies
$\operatorname{\mathcal{A}}(T(w))\subset\operatorname{\mathcal{A}}(T(s(q)))$.
Then the composition $L_{E}(p,q,v)\circ L_{E}(q,r,w)$ is well-defined. By
induction on the length, the result if true for any path.

$\operatorname{\mathfrak{R}}_{\sim}(T)$ defines a lossless compression of $T$.
Proof. As stated in Lemma 3.1, the topology of $T$ can be obtained from
$\operatorname{\mathfrak{R}}_{\sim}(T)$: in other words, we are already able
to reconstruct $T$ without its labels. As it is transparent in the proof, each
vertex $p$ of $\operatorname{\mathfrak{R}}_{\sim}(T)$ corresponds to a
topological subtree of $T$ in the following sense: the multigraph made of $p$
and all its descendants in $\operatorname{\mathfrak{R}}_{\sim}(T)$ is
$\operatorname{\mathfrak{R}}_{\sim}(T(v))$ for some $v\in T$. Here, one aims
to state that the label of node $v$ can be read along a unique path from the
source of $\operatorname{\mathfrak{R}}_{\sim}(T)$ to vertex $p$.

To this end, we consider $(v_{k},\dots,v_{n})$ a path of $T$ (i.e., for any
$k\leq i\leq n-1$, $v_{i+1}\in\operatorname{\text{\bf children}}(v_{i})$) such
that

$\displaystyle\forall\,k\leq i\leq n,\quad$
$\displaystyle[v_{i}]_{\sim}=p_{i},$ $\displaystyle v_{k}=s(p_{k}),$
$\displaystyle\forall\,k+1\leq i\leq n,\quad$ $\displaystyle v_{i}\neq
s(p_{i}).$

We are interested in how to read the label of the nodes of this path from
$\operatorname{\mathfrak{R}}_{\sim}(T)$. There is no difficulty with the first
element: it is obvious that
$\overline{v}_{k}=\overline{s(p_{k})}=L_{V}(p_{k})$. By definition,
$v_{k+1}\in\operatorname{\text{\bf children}}(s(p_{k}))$, thus edge
$(p_{k},p_{k+1},v_{k+1})$ carries the cipher $L_{E}(p_{k},p_{k+1},v_{k+1})$
that transforms labels of $T(s(p_{k+1}))$ into labels of $T(v_{k+1})$. For
instance,

$\displaystyle\overline{v}_{k+1}$
$\displaystyle=L_{E}(p_{k},p_{k+1},v_{k+1})(\overline{s(p_{k+1})})$
$\displaystyle=L_{E}(p_{k},p_{k+1},v_{k+1})(L_{V}(p_{k+1}))$

Now, we complete the path $(v_{k},\dots,v_{n})$ so that it starts from the
root: $(v_{1},\dots,v_{n})$ with $v_{1}=\operatorname{\text{\bf root}}(T)$
and, for any $1\leq i\leq n$, $[v_{i}]_{\sim}=p_{i}$. It should be noted that
one has necessarily $v_{i}=s(p_{i})$ for any $1\leq i\leq k$ (by definition of
$s$). Consequently, edge $(p_{i},p_{i+1},s(p_{i+1}))$, $1\leq i<k$, carries
the cipher $L_{E}(p_{i},p_{i+1},s(p_{i+1}))=\operatorname{\text{\bf id}}$ (see
Lemma 3.1). Therefore, the labels of $T(v_{k+1})$ can be obtained by applying

$\underbrace{L_{E}(p_{1},p_{2},v_{2})}_{=\,\operatorname{\text{\bf
id}}}~{}\circ~{}\cdots~{}\circ~{}\underbrace{L_{E}(p_{k-1},p_{k},v_{k})}_{=\,\operatorname{\text{\bf
id}}}~{}\circ~{}L_{E}(p_{k},p_{k+1},v_{k+1})$

to labels of $T(s(p_{k+1}))$.

This reasoning does not apply to any path: the first element of the path
($v_{k+2},\dots,v_{n})$ is not a child of $s(p_{k+1})$ (whereas $v_{k+1}$ is a
child of $s(p_{k})$). Nevertheless, since $[v_{k+1}]_{\sim}=p_{k+1}$, there
exists a path $(w_{k+2},\dots,w_{n})$ in $T(s(p_{k+1}))$ such that, for any
$i$, $[w_{i}]_{\sim}=[v_{i}]_{\sim}=p_{i}$ and
$w_{k+2}\in\operatorname{\text{\bf children}}(s(p_{k+1}))$. As a consequence,
labels of $T(w_{k+2})$ can be obtained by applying

$L_{E}(p_{k+1},p_{k+2},w_{k+2})$

to labels of $T(s(p_{k+2}))$, which is a subtree of $T(s(p_{k+1}))$. Finally,
labels of $T(v_{k+2})$ can be obtained by applying

$L_{E}(p_{1},p_{2},v_{2})~{}\circ~{}\cdots~{}\circ~{}L_{E}(p_{k-1},p_{k},v_{k})~{}\circ~{}L_{E}(p_{k},p_{k+1},v_{k+1})~{}\circ~{}L_{E}(p_{k+1},p_{k+2},w_{k+2})$

to labels of $T(s(p_{k+2}))$, where the composition makes sense in light of
Lemma 3.1. By recursive induction, this shows that there is a one-to-one
correspondence between nodes of $T$ and paths of
$\operatorname{\mathfrak{R}}_{\sim}(T)$ starting from its source. In addition,
the label of any node of $T$ can be read along the related path of $G$.

An example of DAG-RW compression is provided with Figure 13.

$0$$1$$2$$2$$4$$3$$4$$8$$6$$3$$4$$9$$16$$3$$4$$6$$8$$18$$32$$6$$8$$T$

$0$$1$$2$$3$$3$$\operatorname{\mathfrak{R}}_{\sim}(T)$$\operatorname{\text{\bf
id}}$f$\operatorname{\text{\bf id}}$g$\operatorname{\text{\bf
id}}$$\operatorname{\text{\bf id}}$h$\operatorname{\text{\bf
id}}$h$\operatorname{\text{\bf id}}:x\mapsto x$$\textbf{f}:x\mapsto
2x$$\textbf{g}:x\mapsto x^{2}$$\textbf{h}:3\mapsto 4$

Figure 13: A labelled tree $T$ (left) and its DAG-RW compression
$\operatorname{\mathfrak{R}}_{\sim}(T)$ (right). Nodes are colored according
to their equivalence class with respect to $\sim$. For the sake of
readability, the ciphers $\operatorname{\text{\bf id}}$, f and g are given as
formulae but should be defined only on the alphabet of the subtree to which
they point. In particular, the notation $\operatorname{\text{\bf id}}$ is used
several times but the corresponding ciphers are different.

As explained in Subsection 1.2, DAG compression
$\operatorname{\mathfrak{R}}_{\ast}(T)$, $\ast\in\\{\simeq,\simeq_{l}\\}$, of
a tree $T$, allows its reconstruction up to related isomorphism $\ast$. It is
noteworthy that the situation is different for DAG-RW compression, which is
lossless with respect to $\simeq_{l}$ while built from tree ciphering $\sim$:
the addition of labels on vertices and edges makes possible the exact
reconstruction of node labels.

###  3.2 Compression algorithm

We present here how to build the compressed version
$\operatorname{\mathfrak{R}}_{\sim}(T)$ of $T$ from the topological
compression $\operatorname{\mathfrak{R}}_{\simeq}(T)$ which is computable in
linear time [20]. Since the topology is already evaluated in
$\operatorname{\mathfrak{R}}_{\simeq}(T)$, only the labels of $T$ need to be
taken into account to construct $\operatorname{\mathfrak{R}}_{\sim}(T)$.

The main idea of the algorithm is, in a top-down approach, to replace each
vertex $q$ of $\operatorname{\mathfrak{R}}_{\simeq}(T)$ by new vertices
corresponding to the equivalence classes with respect to $\sim$ of subtrees of
$T$ represented by $q$. By construction, each of the new vertices $r$ has the
same parents $p$ as $q$. However, the value of the section $s(r)$ and the
labels $L_{V}(r)$ and $L_{E}(p,r,v)$, $[v]_{\sim}=r$, need to be defined.

Since we aim to edit $\operatorname{\mathfrak{R}}_{\simeq}(T)$ from top to
bottom, we assume that all the ascendants of $q$ correspond to vertices of
$\operatorname{\mathfrak{R}}_{\sim}(T)$ and that $s$ is defined on them. To
obtain the new vertices $r$ that will replace $q$, we first consider the set
$A_{q}$ of nodes $u$ of $T$ such that $u$ is a child of $s(p)$ of class
$[u]_{\simeq}=q$ for any parent $p$ of $q$. $A_{q}$ is then partitioned
according to the equivalence classes with respect to $\sim$ using the
algorithm for tree ciphering isomorphism given in Section 2: $\mathcal{P}$
denotes this partition and the representative $\sigma(P)$ of the set
$P\in\mathcal{P}$ is arbitrarily chosen to define section $s$ at this level.

Finally, the vertex $q$ is replaced by new vertices $r_{P}$,
$P\in\mathcal{P}$, with label of $\sigma(P)$ and section $s(r_{P})=\sigma(P)$,
which obeys the condition of Lemma 3.1. For each node $v\in P$, we know by
construction that there exists a tree ciphering $\operatorname{\phi}$ between
$T(v)$ and $T(s(r_{p}))$. By the recurrence hypothesis, the vertex
corresponding to $[\operatorname{\text{\bf parent}}(v)]_{\sim}$ exists: an
edge bearing the cipher $f_{\operatorname{\phi}}$ related to
$\operatorname{\phi}$ from it to $r_{p}$ can be created.

Algorithm 7 provides the detail of the compression method, while Figure 14
illustrates it on the tree of Figures 1 and 13.

Input: $T$, $\operatorname{\mathfrak{R}}_{\simeq}(T)$

Output: $\operatorname{\mathfrak{R}}_{\sim}(T)$

1 Init. $R$ as $\operatorname{\mathfrak{R}}_{\simeq}(T)$ and
$s:\emptyset\to\emptyset$

2 foreach  __vertex $q$ of $R$ from its source in breadth-first search order__
do

3 if  _$q$ _is the source of_ $R$_ then

4 $A_{q}\leftarrow\\{\operatorname{\text{\bf root}}(T)\\}$

5 else

6
$A_{q}\leftarrow\displaystyle\bigcup_{\text{edge}\,(p,q)\,\text{of}\,R}\\{u\in\operatorname{\text{\bf
children}}(s(p)):[u]_{\simeq}=q\\}$

7 Init. $\mathcal{P}$ as an empty list and $\sigma:\emptyset\to\emptyset$

8 for  _$u\in A_{q}$_ do

9 if  _$\exists\,P\in\operatorname{\text{dom}}(\sigma)$ _such that_ $T(u)\sim
T(\sigma(P))$_ then

10 Add $u$ to $P$

11 Store the related cipher $f_{\sigma(P),u}$

12 else

13 $P\leftarrow\\{u\\}$

14 Add $P$ to $\mathcal{P}$

15 $\textsc{ExtBij}(\sigma,P,u)$

16

17 for  _$P\in\mathcal{P}$_ do

18 Add a new vertex $r_{P}$ with label $\overline{\sigma(P)}$ to $R$

19 Identify $r_{P}$ as $[\sigma(P)]_{\sim}$

20 foreach  __edge $(q,c)$ of $R$__ do

21 Add a new edge from $r_{P}$ to $c$

22 for  _$u\in P$_ do

23 Add a new edge from $[\operatorname{\text{\bf parent}}(u)]_{\sim}$ to
$r_{P}$ with label $f_{\sigma(P),u}$

24

25 $\textsc{ExtBij}(s,r_{P},\sigma(P))$

26 Delete vertex $q$

return _$R$_

Algorithm 7 DAG-RW

The size of the piece of information stored on the edges (line 16 of Algorithm
7) is linear in the number of labels of the related subtree. In some contexts,
the ciphers can be encoded as formulae instead of by listing values. For
instance, one of the ciphers is the identity from the alphabet of the subtree
to itself. It can also be encoded as an abstract identity function that
returns its argument without specifying the domain. Such an approach can
reduce the amount of information stored on the edges. An example is given in
Figure 13.

$0$$\operatorname{\text{\bf id}}$

$0$$1$$\operatorname{\text{\bf id}}$f

$0$$1$$2$$3$$\operatorname{\text{\bf id}}$f$\operatorname{\text{\bf
id}}$g$\operatorname{\text{\bf id}}$

$0$$1$$2$$3$$3$$\operatorname{\text{\bf id}}$f$\operatorname{\text{\bf
id}}$g$\operatorname{\text{\bf id}}$$\operatorname{\text{\bf
id}}$h$\operatorname{\text{\bf id}}$h

$\operatorname{\text{\bf id}}:x\mapsto x$$\textbf{f}:x\mapsto
2x$$\textbf{g}:x\mapsto x^{2}$$\textbf{h}:3\mapsto 4$

Figure 14: From left to right: state of the graph obtained from
$\operatorname{\mathfrak{R}}_{\simeq}(T)$ after each iteration of Algorithm 7
on the example of Figures 1 and 13. For the sake of readability, the ciphers
$\operatorname{\text{\bf id}}$, f and g are given as formulae. Vertices are
colored according to their equivalence class with respect to $\sim$ for
labelled vertices and to $\simeq$ for unlabelled ones.

The following result gives the complexity of Algorithm 7 as a function of
$C_{\sim}(n)$ that denotes the complexity of the algorithm used for tree
ciphering isomorphism (line 9) on trees of size $n$.

Let $T$ be a tree made of $n$ different topological subtrees: subtree $i$,
$1\leq i\leq n$, is of size $s_{i}$ and appears $n_{i}$ times. The time-
complexity of Algorithm 7 is
$O\left(\\#T\sum_{i=1}^{n}n_{i}C_{\sim}(s_{i})\right)$. Proof. Any vertex $q$
of $\operatorname{\mathfrak{R}}_{\simeq}(T)$ corresponds to a subtree of $T$
that is of size $s_{q}$ and appears $n_{q}$ times. Processing $q$ requires to
evaluate $O(\\#A_{q}^{2})$ isomorphism tests (whose complexity is
$C_{\sim}(s_{q})$) and to copy each of the ciphers in
$O(\\#\operatorname{\mathcal{A}}(T))$ time. Since the number of ciphers is
$O(\\#A_{q})$, the cost of treating $q$ is
$O(\\#A_{q}^{2}C_{\sim}(s_{q})+\\#A_{q}\\#\operatorname{\mathcal{A}}(T))$.
$\\#A_{q}\leq n_{q}$ and $\sum_{q}n_{q}=\\#T$ yield the result.

Since the tree ciphering isomorphism problem is graph isomorphism complete
[10], one can not expect to derive a fast compression algorithm. However, one
can choose to limit the search for isomorphisms (line 9 of Algorithm 7),
either in time or in number of operations, resulting in a possibly incomplete
compression. Numerical results of Subsection 2.5 seem to show that the worst-
case complexity of our algorithm for tree ciphering isomorphism is due to
infrequent pathological cases. One can therefore reasonably anticipate good
compression results even with limited computation time.

###  3.3 Frequent pattern mining

In this subsection, we show how DAG-RW compression can be used to detect
frequent common subtrees with identical label distribution in a tree dataset.

#### DAG-RW compression of a dataset

We consider a dataset of labelled rooted trees $(T_{1},\dots,T_{n})$ and are
interested in the detection of frequent patterns of the following types:
unlabelled subtrees, labelled subtrees, and subtrees with identical label
distribution, i.e. subtrees up to tree ciphering. In other words, we would
like to know, for each of these types of patterns, which ones appear
frequently in the dataset. For the first two, conventional DAG compression
allows the preliminary enumeration of all the patterns, whose frequency is
evaluated in a second step [7]. Here we explore how DAG-RW compression solves
the problem for subtrees with identical label distribution.

To this end, we consider the tree $\mathbb{T}$ whose root has $n$ children:
the roots of the $T_{i}$’s. Then we evaluate its DAG-RW compression
$\operatorname{\mathfrak{R}}_{\sim}(\mathbb{T})$. A vertex $q$ of
$\operatorname{\mathfrak{R}}_{\sim}(\mathbb{T})$ represents a subtree that
appears up to tree ciphering at least once in the dataset. The data which
contain this subtree, $\operatorname{\text{\bf origin}}(q)$, can be
recursively computed in one top-down traversal of the DAG,

$\operatorname{\text{\bf
origin}}(q)=\bigcup_{\text{edge\,$(p,q)$\,of}\,\operatorname{\mathfrak{R}}_{\sim}(\mathbb{T})}\operatorname{\text{\bf
origin}}(p),$

after the following initialisation step: if $p$ is the source of
$\operatorname{\mathfrak{R}}_{\sim}(\mathbb{T})$, $\operatorname{\text{\bf
origin}}(p)=\emptyset$, and, if $p$ is the $i$th vertex connected to the
source, $\operatorname{\text{\bf origin}}(p)=\\{i\\}$. Then
$\\#\operatorname{\text{\bf origin}}(p)/n$ gives the frequency of subtrees
with the same label distribution as $p$ in the dataset. Finally,
$\operatorname{\mathfrak{R}}_{\sim}(\mathbb{T})$ can be filtered to keep the
patterns more frequent than a given threshold.

#### Real data analysis

We conduct frequent pattern mining on two reference datasets from the
literature, INEX 2005 and INEX 2006 [11]. The patterns that we are looking for
are topological subtrees, subtrees with common label distribution, and
labelled subtrees. Topological subtrees and labelled subtrees are detected by
conventional DAG compression [7], while DAG-RW compression is performed for
the detection of subtrees with common label distribution. Both algorithms were
implemented as modules of the Python library treex [6]. Table 1 summarises the
numbers of patterns and frequent patterns (detected in at least $5\%$ of the
data) found in the two datasets. Frequent patterns observed in INEX 2005 and
INEX 2006 are given in Figure 15.

| INEX 2005 | INEX 2006
---|---|---
| # patterns | # frequent patterns | # data | # patterns | # frequent patterns | # data
$\simeq$ | 2073 | 9 |  | 1615 | 11 |
$\sim$ | 2212 | 9 | 4820 | 2430 | 13 | 6053
$\simeq_{l}$ | 5121 | 144 |  | 3165 | 35 |
Table 1: Summary of numbers of patterns and frequent patterns (observed in at
least $5\%$ of the data) detected in datasets INEX 2005 and INEX 2006 for each
of the equivalence relations considered in the paper: $\simeq$ for unlabelled
subtrees, $\sim$ for subtrees with identical label distribution, and
$\simeq_{l}$ for labelled subtrees. INEX 2005

$0$$20$$40$$60$$80$$100$ | $0$$20$$40$$60$$80$$100$ | $0$$20$$40$$60$$80$$100$
---|---|---
$0$$20$$40$$60$$80$$100$ | $0$$20$$40$$60$$80$$100$ | $0$$20$$40$$60$$80$$100$
$0$$20$$40$$60$$80$$100$ | $0$$20$$40$$60$$80$$100$ | $0$$20$$40$$60$$80$$100$

INEX 2006 $0$$20$$40$$60$$80$$100$ | $0$$20$$40$$60$$80$$100$ | $0$$20$$40$$60$$80$$100$
---|---|---
$0$$20$$40$$60$$80$$100$ | $0$$20$$40$$60$$80$$100$ | $0$$20$$40$$60$$80$$100$
$0$$20$$40$$60$$80$$100$ | $0$$20$$40$$60$$80$$100$ | $0$$20$$40$$60$$80$$100$
$0$$20$$40$$60$$80$$100$ | $0$$20$$40$$60$$80$$100$ | $0$$20$$40$$60$$80$$100$
| $0$$20$$40$$60$$80$$100$ |

Figure 15: Common subtrees with identical label distribution appearing in at
least $5\%$ of trees from INEX 2005 (top) and INEX 2006 (bottom) datasets:
gray bar gives the frequency of each of them (scale from $0\%$ to $100\%$).
Each pattern corresponds to at least 1 subtree with labels under equivalence
relation $\simeq_{l}$: black bars give their frequency when larger than $5\%$
(horizontal red line).

In light of the inclusion relation (1) between the three types of patterns,
theory says that the number of topological subtrees is less than the number of
subtrees with common label distribution, which is less than the number of
labelled subtrees. Of course, we observe this phenomenon in the data but also
note that the number of labelled subtrees found in INEX 2005 is larger than
the number of data itself, which says that shared labelled subtrees are not so
frequent in this dataset. The relation between tree isomorphisms does not tell
us anything about the frequency of observed patterns, which highly depends on
the distribution of the data. We can nevertheless expect more frequent
patterns from a more frequent pattern type. The number of frequent topological
subtrees is $9$ in INEX 2005 and $11$ in INEX 2006, which gives parsimonious
representations of the datasets. With respectively $9$ and $13$ frequent
occurrences, subtrees with identical label distribution provide a
representation as parsimonious as topological subtrees but preserve the label
distribution, which gives an additional insight on the data. Labelled subtrees
keep the information of labels but require respectively $144$ and $35$
frequent patterns to describe the data, which is, in particular for INEX 2005,
much less parsimonious.

The subtree with only one node, whatever its label, is present in any subtree
under both $\simeq$ and $\sim$, which implies a frequency of $100\%$ in the
two datasets. This hides a diversity of labels ($119$ frequent labelled leaves
in INEX 2005 and $11$ in INEX 2006), which can be investigated without taking
into account the topology (trivial in this case). This phenomenon occurs, to a
lesser extent, for other patterns, e.g. $(1,3)$ (first row, third column) in
INEX 2005 and $(1,3)$ in INEX 2006. DAG-RW compression allows to discover,
without losing the information of the label distribution, that some subtrees
are very frequent. Typically, subtree $(1,2)$ in INEX 2005 is present, up to
tree ciphering, in $96\%$ of data, while the frequency of its most frequent
labelled version is only $25\%$. In addition, it avoids to miss patterns: $5$
frequent subtrees in INEX 2005 and $1$ in INEX 2006 have no labelled version
more frequent than $5\%$. To sum up, in both datasets, identifying frequent
labelled subtrees lead to much more patterns and less diversity of topologies
than subtrees with identical label distribution. Furthermore, contrary to
topological patterns, DAG-RW compression separates common topologies with
different label distributions, e.g. patterns $(1,2)$ and $(1,3)$ in INEX 2006.
As a conclusion, with a representation as parsimonious as from topology only
(without losing the label distribution), and a much more parsimonious
representation together with a greater diversity of topologies than from
labelled patterns, DAG-RW compression achieves a relevant frequent pattern
mining on these datasets.

## References

  * [1] Aggarwal, C. C., Bhuiyan, M. A., and Hasan, M. A. Frequent pattern mining algorithms: A survey.  In Frequent pattern mining. Springer, 2014, pp. 19–64.
  * [2] Aho, A., Hopcroft, J., and Ullman, J. The Design and Analysis of Computer Algorithms.  Addison-Wesley series in computer science and information processing. Addison-Wesley Publishing Company, 1974.
  * [3] Asai, T., Arimura, H., Uno, T., and Nakano, S.-i. Discovering frequent substructures in large unordered trees.  In Discovery Science (Berlin, Heidelberg, 2003), G. Grieser, Y. Tanaka, and A. Yamamoto, Eds., Springer Berlin Heidelberg, pp. 47–61.
  * [4] Astrachan, O. Bubble sort: an archaeological algorithmic analysis.  ACM Sigcse Bulletin 35, 1 (2003), 1–5.
  * [5] Avis, D., and Fukuda, K. Reverse search for enumeration.  Discrete Applied Mathematics 65, 1 (1996), 21–46.  First International Colloquium on Graphs and Optimization.
  * [6] Azaïs, R., Cerutti, G., Gemmerlé, D., and Ingels, F. treex: a Python package for manipulating rooted trees.  Journal of Open Source Software 4, 38 (2019), 1351.
  * [7] Azaïs, R., and Ingels, F. The weight function in the subtree kernel is decisive.  The Journal of Machine Learning Research 21, 1 (2020), 2535–2570.
  * [8] Babai, L. Graph isomorphism in quasipolynomial time.  In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (2016), pp. 684–697.
  * [9] Babilon, R., Matoušek, J., Maxová, J., and Valtr, P. Low-distortion embeddings of trees.  In Graph Drawing (2002), Springer Berlin Heidelberg, pp. 343–351.
  * [10] Booth, K. S., and Colbourn, C. J. Problems polynomially equivalent to graph isomorphism.  Computer Science Department, Univ., 1979.
  * [11] Denoyer, L., Gallinari, P., and Vercoustre, A.-M. Report on the XML Mining Track at INEX 2005 and INEX 2006, Categorization and Clustering of XML Documents.  In 5th International Workshop of the Initiative for the Evaluation of XML Retrieval, INEX 2006 (Dagstuhl, Germany, Dec. 2006), N. Fuhr, M. Lalmas, S. Malik, and G. Kazai, Eds., vol. 4518 of Lecture Notes in Computer Science, Springer, pp. 432–443.
  * [12] Fortin, S. The graph isomorphism problem.  Tech. rep., University of Alberta, Canada, 1996.
  * [13] Grohe, M., Schweitzer, P., and Wiebking, D. Deep Weisfeiler Leman.  In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA) (2021), SIAM, pp. 2600–2614.
  * [14] Ingels, F., and Azaïs, R. Isomorphic unordered labeled trees up to substitution ciphering.  In Combinatorial Algorithms (2021), pp. 385–399.
  * [15] Ingels, F., and Azaïs, R. Enumeration of irredundant forests.  Theoretical Computer Science (2022).
  * [16] Jiménez, A., Berzal, F., and Cubero, J.-C. Frequent tree pattern mining: A survey.  Intell. Data Anal. 14 (01 2010), 603–622.
  * [17] Knuth, D. E. The Art of Computer Programming, Volume 4, Fascicle 2: Generating All Tuples and Permutations (Art of Computer Programming).  Addison-Wesley Professional, 2005.
  * [18] McKay, B. D., and Piperno, A. Practical graph isomorphism, ii.  Journal of symbolic computation 60 (2014), 94–112.
  * [19] Schöning, U. Graph isomorphism is in the low hierarchy.  Journal of Computer and System Sciences 37, 3 (1988), 312–323.
  * [20] Valiente, G. An efficient bottom-up distance between trees.  In Proceedings Eighth Symposium on String Processing and Information Retrieval (2001), pp. 212–219.
  * [21] Valiente, G. Algorithms on Trees and Graphs.  Springer Science & Business Media, 2013.
  * [22] Weisfeiler, B., and Lehman, A. A reduction of a graph to a canonical form and an algebra arising during this reduction.  Nauchno-Technicheskaya Informatsia 2, 9 (1968), 12–16.
  * [23] Zaki, M. J. Efficiently mining frequent trees in a forest.  In Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (New York, NY, USA, 2002), KDD ’02, Association for Computing Machinery, pp. 71–80.
  * [24] Zhang, Y., and Zhang, Y. Z. On the number of leaves in a random recursive tree.  Brazilian Journal of Probability and Statistics 29, 4 (2015), 897–908.

##  Appendix A Evolution of the size of the search space

This appendix investigates how the various manipulations of the system
presented in Section 2 modify the size of the search space, defined in (3) as
the number of possible ways to complete $\operatorname{\phi}$ from a
distribution of nodes (not already mapped via $\operatorname{\phi}$) between
bags and collections.

###  A.1 Reduction factors

#### Splitting bags

When a bag of size $n$ is split in two due to the action of SplitChildren, say
into bags of size $p$ and $n-p$, then we go from $n!$ possibilities to
$p!(n-p)!$, reducing the space by a factor $\binom{n}{p}$.

#### Splitting collections

When SplitChildren is applied to a collection, several sets can be split and
put together in the same collection. Assume that we split $k$ sets of size $n$
into sets of size $p$ and $n-p$,
$k\leq\min(\\#\mathbf{C}_{n},\operatorname{\text{\bf deg}}(T))$. Then we go
from $\\#\mathbf{C}_{n}!\times n!^{\\#\mathbf{C}_{n}}$ possibilities to
$(\\#\mathbf{C}_{n}-k)!\times n!^{\\#\mathbf{C}_{n}-k}\times k!p!^{k}\times
k!(n-p)!^{k}$. The space is therefore modified by a factor
$\displaystyle\frac{1}{k!}\binom{\\#\mathbf{C}_{n}}{k}\binom{n}{p}^{k}$, which
is not always greater than $1$. However, this does not show that the search
space can grow because all the parameters are highly interrelated: the values
for which the reduction factor is less than $1$ may not be feasible. We
actually exhibit in Appendix A.2 an instance of a tree for which the search
space locally grows along the algorithm.

#### Mapping parents

When recursively mapping the parents of two nodes, if they were present in a
bag $\mathbf{B}$, we go from $\\#\mathbf{B}!$ to $(\\#\mathbf{B}-1)!$,
reducing the space by a factor $\\#\mathbf{B}$; if they were present in a
collection $\mathbf{C}_{n}$, then we go from $\\#\mathbf{C}_{n}!\times
n!^{\\#\mathbf{C}_{n}}$ possibilities to $(\\#\mathbf{C}_{n}-1)!\times
n!^{\\#\mathbf{C}_{n}-1}\times(n-1)!$, reducing the space by a factor
$n\\#\mathbf{C}_{n}$.

#### Deductions rules

When applying Deduction Rule 2.3 and splitting a collection $\mathbf{C}_{n}$
into two new collections $\mathbf{C}^{\prime}_{n}$ and
$\mathbf{C}^{\prime\prime}_{n}$, say $\\#\mathbf{C}_{n}=p+q$,
$\\#\mathbf{C}^{\prime}_{n}=p$ and $\\#\mathbf{C}^{\prime\prime}_{n}=q$, then
we go from $(p+q)!\times n!^{p+q}$ possibilities to $p!\times n!^{p}\times
q!\times n!^{q}$, reducing the space by a factor $\binom{p+q}{q}$. On the
other hand, Deduction Rules 2.2, 2.3 and 2.3 do not modify the size of the
search space. However, these rules still modify the system in an irrevocable
way: mapping nodes (Deduction Rule 2.2), mapping labels (Deduction Rule 2.3)
or transferring nodes from a collection to a bag (Deduction Rule 2.3).

###  A.2 Does the search space only shrink? A counterexample

The following example shows that the search space can locally grow through the
deduction steps given in Subsections 2.2 and 2.3.

Step 1/6 (histogram of labels)

$N(\operatorname{\mathbb{B}},\operatorname{\mathbb{C}})=12!=479,001,600$

$A$$u_{1}$$A$$u_{2}$$B$$u_{3}$$B$$u_{4}$$C$$u_{5}$$D$$u_{6}$$E$$u_{7}$$F$$u_{8}$$C$$u_{9}$$D$$u_{10}$$E$$u_{11}$$F$$u_{12}$

Step 2/6 (depth)

$N(\operatorname{\mathbb{B}},\operatorname{\mathbb{C}})=3!\times 8!=241,920$

$A$$u_{1}$$A$$u_{2}$$B$$u_{3}$$B$$u_{4}$$C$$u_{5}$$D$$u_{6}$$E$$u_{7}$$F$$u_{8}$$C$$u_{9}$$D$$u_{10}$$E$$u_{11}$$F$$u_{12}$

Step 3/6 (equivalence class)

and step 4/6 (parents)

$N(\operatorname{\mathbb{B}},\operatorname{\mathbb{C}})=2!\times 8!=80,640$

$A$$u_{1}$$A$$u_{2}$$B$$u_{3}$$B$$u_{4}$$C$$u_{5}$$D$$u_{6}$$E$$u_{7}$$F$$u_{8}$$C$$u_{9}$$D$$u_{10}$$E$$u_{11}$$F$$u_{12}$

Step 5/6 (from bags to collections)

$N(\operatorname{\mathbb{B}},\operatorname{\mathbb{C}})=\left(2!\times
1!^{2}\right)\times\left(4!\times 2!^{4}\right)=768$

$A$$u_{2}$$B$$u_{3}$$n=1$$C_{1}$$\mathbf{C}$$C$$u_{5}$$C$$u_{9}$$D$$u_{6}$$D$$u_{10}$$E$$u_{7}$$E$$u_{11}$$F$$u_{8}$$F$$u_{12}$$n=2$$C^{\prime}_{1}$$\mathbf{C^{\prime}}$

At this stage, Deduction Rule 2.3 splits $u_{2}$ and $u_{3}$ from
$\mathbf{C}_{1}$ using mapped labels ($A$ and $B$), which yields
$N(\operatorname{\mathbb{B}},\operatorname{\mathbb{C}})=4!\times 2!^{4}=384$
(from $\mathbf{C}^{\prime}_{2}$ only).

From one of these new collections (say the one with $u_{2}$), one can create a
bag that will map $u_{2}$ and its counterpart thanks to Deduction Rule 2.2.
This does not change the size of the search space.

SplitChildren is then called on $\mathbf{C}^{\prime}_{2}$ to isolate nodes
$u_{5}$, $u_{6}$, $u_{7}$ and $u_{8}$ (children of $u_{2}$) and nodes $u_{9}$,
$u_{10}$, $u_{11}$ and $u_{12}$ (children of $u_{3}$). One obtains the
following partition.

$C$$u_{5}$$D$$u_{6}$$E$$u_{7}$$F$$u_{8}$$n=1$$C^{\prime\prime}_{1}$$\mathbf{C^{\prime\prime}}$$C$$u_{9}$$D$$u_{10}$$E$$u_{11}$$F$$u_{12}$$n=1$$C^{\prime\prime\prime}_{1}$$\mathbf{C^{\prime\prime\prime}}$

The related cardinality is
$N(\operatorname{\mathbb{B}},\operatorname{\mathbb{C}})=\left(4!\times
1!^{4}\right)^{2}=576$, which illustrates a local growth of the search space.
It should be however noticed that any mapping of labels in one of the
collections yields a deduction in the other: the 576 mappings are not all
feasible.

##  Appendix B Optimizing the number of states of the backtracking tree

When it comes to backtracking in Subsection 2.4, the aim is to explore the
various possible associations between, on the one hand, nodes within bags and,
on the other hand, sets within collections. Any backtracking strategy for
exploring these choices implicitly induces a tree structure, with leaves
representing terminal states. The smaller the tree, the more efficient the
algorithm is likely to be. In this appendix, we develop a mathematical model
of the size of this tree and derive a backtracking strategy to minimise it.

###  B.1 Preliminaries

#### Enumeration of permutations

Enumerating all possible mappings between the nodes of a bag, or all the bags
that can be constructed by associating the sets of a collection, amounts in
both cases to enumerating permutations. We assume that we have two sets of
$n\geq 2$ objects to be associated together. The associated enumeration tree
has $n!$ leaves (one for each permutation of $\\{1,\dots,n\\}$) and as many
internal nodes as necessary to build these $n!$ permutations by mapping only
one additional pair of objects at a time.

The size of the enumeration tree (except the root) $a_{n}$ is the number of
operations required to construct all the permutations of $n$ elements [17],

$a_{n}=n!\sum_{i=1}^{n-1}\frac{1}{i!}.$ (4)

It should be noted that $a_{n}$ satisfies the recurrence equation
$a_{n}=n(1+a_{n-1})$ with $a_{1}=0$.

#### Nesting enumeration trees

The tree introduced above only allows to build mappings between one pair of
sets of objects, but, in our case, the system is made of several pairs of sets
of objects to be mapped together. We assume that we have two sets of $p\geq 2$
objects on the one hand, and two sets of $q\geq 2$ objects on the other.

Since we have to enumerate the $p!$ permutations of the first pair, and the
$q!$ permutations of the second pair, and since these permutations are
independent, we can build mappings incrementally, one pair of objects at a
time, in any desired way.

Our aim here is to minimise the size of the overall enumeration tree. Let
$a_{p,q}$ be the size of the optimal enumeration tree for those two pairs of
respective size $p$ and $q$. It is easy to see that $a_{2,2}=6$,
$a_{p,1}=a_{p}$ and $a_{1,q}=a_{q}$. In the general case of an instance of
size $(p,q)$, we can map two objects from the pair of size $p$ (which leads to
a new instance of size $(p-1,q)$), or from the pair of size $q$ (which leads
to a new instance of size $(p,q-1)$). Therefore, $a_{p,q}$ verifies the
following recurrence relation, echoing the one of $a_{n}$,

$a_{p,q}=\min\big{[}p(1+a_{p-1,q}),q(1+a_{p,q-1})\big{]}.$

We have the following result.

For any $p\geq 2$ and $q\geq 2$,
$a_{p,q}=a_{\min(p,q)}+(\min(p,q))!a_{\max(p,q)}$. Proof. We assume $p\leq q$
without loss of generality and proceed by induction on $p$ and $q$. One can
remark that $a_{2,2}=a_{2}+2!a_{2}$ and $a_{1,q}=a_{1}+1!a_{q}$. From now on,
we assume that the result is verified for all couples
$(p^{\prime},q^{\prime})$ so that either $p^{\prime}\leq p$ and
$q^{\prime}<q$, or $p^{\prime}<p$ and $q^{\prime}\leq q$.

If we perform a mapping on the pair of size $p$, then $p-1\leq q$ and, by
induction, $a_{p-1,q}=a_{p-1}+(p-1)!a_{q}$, i.e.
$p(1+a_{p-1,q})=a_{p}+p!a_{q}$ after simplification.

If we perform a mapping on the pair of size $q$, then two cases can occur:
either $q-1<p$ (in which case, $p=q$) or $p\leq q-1$. In the first case, with
$p=q$, we have $a_{p,q-1}=a_{q-1}+(q-1)!a_{p}$ by induction, i.e.
$q(1+a_{p,q-1})=a_{q}+q!a_{p}=a_{p}+p!a_{q}$ after simplification.
Consequently, $a_{p,q}=a_{p}+p!a_{q}$ as claimed.

In the second case $p\leq q-1$, we have $a_{p,q-1}=a_{p}+p!a_{q-1}$ by
induction, then, with $qa_{q-1}=a_{q}-q$,
$q(1+a_{p,q-1})=q(1+a_{p}+p!a_{q-1})=q(1+a_{p})+p!(a_{q}-q)$. Thus, we need to
show

$q(1+a_{p})+p!(a_{q}-q)\geq a_{p}+p!a_{q},$

which is equivalent to

$\frac{1}{p!}+\left(1-\frac{1}{q}\right)\frac{a_{p}}{p!}\geq 1.$

Since $p\leq q$, $1-1/q\geq 1-1/p$, so it suffices to prove that
$\displaystyle\frac{1}{p!}+\left(1-\frac{1}{p}\right)\sum_{i=1}^{p-1}\frac{1}{i!}\geq
1$ for any $p\geq 2$. This holds for $p=2$. In addition,
$\left(1-\frac{1}{p}\right)\displaystyle\sum_{i=1}^{p-1}\frac{1}{i!}$ is an
increasing function of $p$ whose value at $p=3$ is $1$, which states the
result for any $p\geq 3$.

Consequently, $a_{p,q}$ is the size of the enumeration tree that begins with
the permutations of the set of size $\min(p,q)$, followed, for each of its
$\min(p,q)!$ leaves by the permutations of set of size $\max(p,q)$ (see Figure
16). It is therefore optimal to enumerate first the permutations of the
smallest set, then the ones of the largest set.

Furthermore, by immediate induction, if we have to process more than two pairs
of sets of objects, the permutation tree size is minimal if we process them by
increasing size.

$\bullet$$a_{p}$$\bullet$$\dots$$\bullet$$a_{q}$$a_{q}$$p!$

Figure 16: Optimal nesting of two permutation trees for two pairs of sets of
respective size $p$ and $q$, $p\leq q$.

This result can easily be related to the original problem of backtracking: if
there are only bags in the system, then they must be processed in increasing
size in order to obtain the smallest possible enumeration tree. However, this
does not allow to simultaneously manage bags and collections at this point.

###  B.2 Model of the size of the backtracking tree

Given a finite sequence of integer tuples $(n_{i},\alpha_{i})$, $1\leq i\leq
p$, with $n_{i}\geq 2$ and $\alpha_{i}\geq 1$, we define the following
variadic function,

$f\left((n_{1},\alpha_{1}),\dots,(n_{p},\alpha_{p})\right)=\begin{cases}\alpha_{1}a_{n_{1}}&\text{if
}$p=1$,\\\
\alpha_{1}\left[a_{n_{1}}+n_{1}!f\left((n_{2},\alpha_{2}),\dots,(n_{p},\alpha_{p})\right)\right]&\text{otherwise}.\end{cases}$
(5)

When appropriate tuples are chosen, the value of $f$ corresponds to the size
of the backtracking tree (up to the root) associated with the enumeration of
mappings from bags and collections, according to the following principles.

#### Link between $f$ and bags

We saw in the previous section that, if we have two bags of sizes $n$ and $m$,
treating them in this order induces a backtracking tree of size
$1+a_{n}+n!a_{m}$. If we now have $p$ bags of respective sizes
$n_{1},\dots,n_{p}$, and we process them in this order, then the resulting
tree has $1+f\left((n_{1},1),\dots,(n_{p},1)\right)$ states. In other words, a
bag of size $n$ processed in position $k$ contributes to the backtracking tree
as the tuple $(n,1)$ as $k$th input variable of $f$. It should be recalled
that Lemma B.1 proves that the backtracking tree size is minimal when bags are
processed in increasing order.

#### Link between $f$ and collections

We explained in Subsection 2.4 that two strategies can be considered for
processing collections. Let $\mathbf{C}$ be a collection and
$n\in\operatorname{\text{supp}}(\mathbf{C})$:

  * •

either we create all $\\#\mathbf{C}_{n}!$ possible bags by associating the
subsets of $\mathbf{C}_{n}$, then we process these bags one after the other;

  * •

or we create a bag, we process it entirely, then we create an other bag (from
the collection that now contains $\\#\mathbf{C}_{n}-1$ subsets), which we
process entirely, and so on.

In terms of backtracking tree size, by definition (5) of $f$, the first
strategy amounts to considering as input variables of $f$ the tuple
$(\\#\mathbf{C}_{n},1)$ first then $\\#\mathbf{C}_{n}$ times the tuple
$(n,1)$. The second strategy amounts to considering the tuple
$(n,\\#\mathbf{C}_{n})$ first (one branches on $\\#\mathbf{C}_{n}$
possibilities – mapping the first set of $C_{1,n}$ with each of the others
from $C_{2,n}$ –, then process the tree generated by a bag of size $n$), then
the tuple $(n,\\#\mathbf{C}_{n}-1)$, and so on to the tuple $(n,1)$. We state
in the following lemma that the second strategy minimises $f$ and thus the
size of the resulting backtracking tree, establishing incidentally Proposition
2.4.

For any $n\geq 2$ and $\alpha\geq 2$,

$f\big{(}(n,\alpha),(n,\alpha-1),\dots,(n,1)\big{)}<f\big{(}(\alpha,1),\underbrace{(n,1),\dots,(n,1)}_{\alpha}\big{)}.$

Proof. By induction on $\alpha$,

$\displaystyle f\big{(}(n,\alpha),(n,\alpha-1),\dots,(n,1)\big{)}$
$\displaystyle=$ $\displaystyle
a_{n}\displaystyle\sum_{k=0}^{\alpha-1}\frac{\alpha!}{(\alpha-1-k)!}(n!)^{k},$
$\displaystyle f\big{(}\underbrace{(n,1),\dots,(n,1)}_{\alpha}\big{)}$
$\displaystyle=$ $\displaystyle
a_{n}\displaystyle\sum_{k=0}^{\alpha-1}(n!)^{k},$

which shows

$f\big{(}(\alpha,1),\underbrace{(n,1),\dots,(n,1)}_{\alpha}\big{)}=a_{\alpha}+\alpha!a_{n}\displaystyle\sum_{k=0}^{\alpha-1}(n!)^{k}.$

The conclusion is immediate when comparing term by term each of the two sums.

The second strategy is therefore adopted in Algorithm 5. Consequently, a
collection $\mathbf{C}_{n}$ contributes to the backtracking tree size as the
tuples $(n,\\#\mathbf{C}_{n}),\dots,(n,1)$ as input variables of $f$. The size
of the backtracking tree generated by $\mathbf{C}_{n}$ is thus expressed as
$1+f\big{(}(n,\\#\mathbf{C}_{n}),(n,\\#\mathbf{C}_{n}-1),\dots,(n,1)\big{)}$.

#### General case: bags and collections

When the remaining search space is organised with both bags and collections, a
bag $\mathbf{B}$ processed in position $k$ contributes to the backtracking
tree size as $\left(b+\sum_{i=1}^{c}\\#\mathbf{C}_{n_{i}}\right)$-th input
variable $(\\#\mathbf{B},1)$, with $b$ the number of bags processed before $k$
and $c$ the number of collections $\mathbf{C}_{n_{i}}$ processed before $k$; a
collection $\mathbf{C}$ contributes as input variables
$(n,\\#\mathbf{C}_{n}),\dots,(n,1)$ at positions
$b+\sum_{i=1}^{c}\\#\mathbf{C}_{n_{i}}$, …,
$b+\sum_{i=1}^{c}\\#\mathbf{C}_{n_{i}}+\mathbf{C}_{n}-1$.

The construction of the backtracking tree whose size is estimated by $f$
assumes that the permutation trees obtained from bags and collections are
independent, i.e. that no branches are pruned thanks to deductions, recursive
parent mapping, or SplitChildren, contrary to what is implemented in Algorithm
5. In other words, the model developed in this section provides an upper-bound
of the actual backtracking tree size.

###  B.3 Proof of Proposition 2.4

We begin with the following lemma.

For any $p\geq 1$, $(n_{i})_{1\leq i\leq p}$ and $(\alpha_{i})_{1\leq i\leq
p}$ with $n_{i}\geq 2$ and $\alpha_{i}\geq 1$,

$f\left((n_{1},\alpha_{1}),\dots,(n_{p},\alpha_{p})\right)\leq(e-1)\displaystyle\prod_{i=1}^{p}\alpha_{i}n_{i}!\displaystyle\sum_{i=0}^{p-1}\frac{1}{2^{i}}.$

Proof. The proof is made by induction on $p$. One has
$f\left((n,\alpha)\right)=\alpha a_{n}\leq(e-1)\alpha n!$, which shows the
result for $p=1$. Now, if $p\geq 2$, we have

$\displaystyle f\left((n_{1},\alpha_{1}),\dots,(n_{p},\alpha_{p})\right)$
$\displaystyle=\alpha_{1}\left[a_{n_{1}}+n_{1}!f\left((n_{2},\alpha_{2}),\dots,(n_{p},\alpha_{p})\right)\right]$
$\displaystyle\leq(e-1)\alpha_{1}n_{1}!\left(1+\prod_{i=2}^{p}\alpha_{i}n_{i}!\sum_{i=0}^{p-2}\frac{1}{2^{i}}\right)$
$\displaystyle=(e-1)\prod_{i=1}^{p}\alpha_{i}n_{i}!\left(\frac{1}{\prod_{i=2}^{p}\alpha_{i}n_{i}!}+\sum_{i=0}^{p-2}\frac{1}{2^{i}}\right)$
$\displaystyle\leq(e-1)\prod_{i=1}^{p}\alpha_{i}n_{i}!\sum_{i=0}^{p-1}\frac{1}{2^{i}},$

with $\prod_{i=2}^{p}\alpha_{i}n_{i}!\geq 2^{p-1}$ for $\alpha_{i}\geq 1$ and
$n_{i}\geq 2$.

We now connect the stated inequality with the system made of bags and
collections according to the principles developed in Appendix B.2. As
previously explained, replacing the input tuples of $f$ by well-chosen
parameters, the left-hand term models the size of the backtracking tree. In
addition, the factor $\prod_{i=1}^{p}\alpha_{i}n_{i}!$ of the upper-bound can
be interpreted as follows.

  * •

A bag $\mathbf{B}$ is represented by the tuple $(\\#\mathbf{B},1)$ and
therefore contributes as $\\#\mathbf{B}!$ to the product.

  * •

A collection $\mathbf{C}_{n}$, $n\in\operatorname{\text{supp}}(\mathbf{C})$,
is related to the tuples $(n,\\#\mathbf{C}_{n})$, $(n,\\#\mathbf{C}_{n}-1)$,
…, $(n,1)$, contributing as $n!^{\\#\mathbf{C}_{n}}\\#\mathbf{C}_{n}!$ to the
product. As aforementioned, a collection can be processed in an alternative
way corresponding to the tuple $(\\#\mathbf{C}_{n},1)$ first then
$\\#\mathbf{C}_{n}$ times the tuple $(n,1)$. This leads to a larger
backtracking tree but contributes as the same factor.

As a consequence, we retrieve formula (3) of
$N(\operatorname{\mathbb{B}},\operatorname{\mathbb{C}})$. Bounding the
remaining sum by $2$ leads to the expected result. It should be noted that
this upper-bound is valid whether or not we select the order of tuples to
minimise $f$ (and also does not depend on the strategy used to process
collections).

###  B.4 Proof of Theorem 2.4

Given $p\geq 2$ tuples $(n_{i},\alpha_{i})$, $n_{i}\geq 2$ and $\alpha_{i}\geq
1$, and denoting the first two $(m,\alpha)$ and $(n,\beta)$, we are interested
in the conditions on $m$, $n$, $\alpha$ and $\beta$ under which one has

$\Delta
f=f\left((m,\alpha),(n,\beta),\dots,(n_{p},\alpha_{p})\right)-f\left((n,\beta),(m,\alpha),\dots,(n_{p},\alpha_{p})\right)\leq
0.$

If $\Delta f\leq 0$, the objects corresponding to tuples $(m,\alpha)$ and
$(n,\beta)$ must be processed in this order to minimise the size of the
backtracking tree. On the other hand, if $\Delta f>0$, they have to be
swapped.

By virtue of the bubble sort principle [4] and taking into account the
recursive form (5) of $f$, it is enough to know when to swap the first two
arguments to globally minimise $f$. Indeed, we can recursively permute the
subsequent elements and determine the absolute minimum of $f$.

With some elementary manipulations on the definition (5) of $f$, $\Delta f$
can be rewritten as

$\Delta f=\beta a_{n}(\alpha m!-1)-\alpha a_{m}(\beta n!-1).$ (6)

We now assume $m\geq n$ without loss of generality and examine the following
cases.

  * •

If $m=n$, then $\Delta f=a_{m}(\alpha-\beta)$ which shows that the tuple
$(m,\min(\alpha,\beta))$ must be placed first to minimise $f$.

  * •

If $m>n$ and $\beta\geq 2$, then, in light of the first item of upcoming Lemma
B.4, the tuple $(m,\alpha)$ must be placed first to minimise $f$, whatever the
value of $\alpha$.

  * •

If $m>n$ and $\beta=1$, then, in light of the second item of upcoming Lemma
B.4, the tuple $(n,\beta)=(n,1)$ must be placed first to minimise $f$,
whatever the value of $\alpha$.

We assume $m>n$.

  * •

If $\beta\geq 2$, then $\Delta f<0$.

  * •

If $\beta=1$, then $\Delta f>0$.

Proof. The proof can be found in Appendix B.5.

The strategy for dealing with bags and collections implemented in Algorithm 5
has been derived from the previous results to minimise the size of the
backtracking tree:

  * •

If the system is composed of bags and collections, since bags correspond to
tuples $(n,1)$ and collections to tuples $(m,\alpha)$ with $\alpha\geq 2$,
then bags have to be processed first.

  * •

If there are only bags left, i.e. $\alpha_{i}=1$ for all $i$, they have to be
processed by increasing size (as already stated in Lemma B.1).

  * •

If there are only collections $\mathbf{C}_{n}$ and $\mathbf{C}_{m}^{\prime}$
with $n>m$ left, then $\mathbf{C}_{n}$ has to be processed first. If $n=m$,
then $\mathbf{C}_{n}$ has to be processed first if
$\\#\mathbf{C}_{n}\leq\\#\mathbf{C}^{\prime}_{m}$.

###  B.5 Proof of Lemma B.4

For any $n\geq 1$ and $k\geq 1$, we denote

$b_{n}=\sum_{i=1}^{n-1}\frac{1}{i!},\qquad
r_{n}=\sum_{i=n}^{\infty}\frac{1}{i!}\qquad\text{and}\qquad
s_{n,k}=b_{n+k}-b_{n}.$

Consequently, with (4), $a_{n}=n!b_{n}$, $b_{n}+r_{n}=e-1$, and $n!\leq
a_{n}\leq(e-1)n!$. In addition, together with (6),

$\Delta f=\alpha\beta b_{n}n!m!\left[1-\frac{1}{\alpha
m!}-\frac{b_{m}}{b_{n}}\left(1-\frac{1}{\beta n!}\right)\right].$

If we assume moreover that $m>n$, then, with $k=m-n$,

$\Delta f=-\alpha\beta
b_{n}n!(n+k)!\left(\frac{1}{\alpha(n+k)!}+\frac{s_{n,k}(\beta
n!-1)-b_{n}}{b_{n}\beta n!}\right).$ (7)

#### First item

In light of (7), $\Delta f<0$ is equivalent to

$\displaystyle\frac{1}{\alpha(n+k)!}+\frac{s_{n,k}(\beta
n!-1)-b_{n}}{b_{n}\beta n!}>0.$

It suffices to show that the right-hand term is nonnegative, i.e.
$s_{n,k}(\beta n!-1)\geq b_{n}$. Since $s_{n,k}$ is increasing with $k$, we
only need to investigate the case $k=1$, which is equivalent to
$\beta-1/n!\geq b_{n}$ because $s_{n,1}=1/n!$. This is equivalent to
$\beta\geq b_{n+1}$, which is true because $b_{n}$ is bounded by $e-1$.

#### Second item

In light of (7), $\Delta f>0$ is equivalent after some elementary
manipulations to

$\frac{1}{s_{n,k}}\left(1-\frac{n!}{\alpha(n+k)!}\right)>\frac{n!-1}{b_{n}},$

which we shall establish by a disjunction of cases on $n$.

  * •

We assume $n=2$. It should be remarked that it is sufficient to investigate
the case $\alpha=1$. Assuming $\alpha=1$ and multiplying each side of the
inequality by $s_{2,k}$, the expected result is equivalent to

$\sum_{i=2}^{k+2}\frac{1}{i!}<1-\frac{1}{(k+2)!},$

which is true because the left-hand term is upper-bounded by $e-2$ and the
right-hand term is lower-bounded by $5/6$.

  * •

From now on, we assume $n\geq 3$. Since $\alpha\geq 1$ and $k\geq 1$, it is
easy to see that

$\frac{1}{s_{n,k}}\left(1-\frac{n!}{\alpha(n+k)!}\right)>\frac{n}{s_{n,k}(n+1)}.$

Consequently, it is sufficient to prove

$\frac{1}{s_{n,k}}\frac{n}{n+1}>\displaystyle\frac{n!-1}{b_{n}}.$

The left-hand term being a decreasing function of $k$, the inequality holds if
we can establish it at the limit. As a consequence, we want to prove

$(n!-1)\left(1+\frac{1}{n}\right)\frac{r_{n}}{e-1-r_{n}}<1.$

    * –

If $n=3$, with $r_{3}=e-5/2$, the left-hand term is approximately evaluated to
$0.97<1$.

    * –

If $n\geq 4$, with $n!-1<n!$, we bound the left-hand term by
$(1+1/n)n!r_{n}/(e-1-r_{n})$ which is a decreasing function of $n$ (as a
product of decreasing functions of $n$). In addition, the term corresponding
to $n=4$ is approximately evaluated to $0.92<1$.