# Nearest Embedded and Embedding Self-Nested Trees
## 1 Introduction  
Trees form a wide family of combinatorial objects that offers many application fields, e.g., plant modeling and XML files analysis. Modern databases are huge and thus stored in compressed form. Compression methods take advantage of repeated substructures appearing in the tree. As explained in [1], one often considers the following two types of repeated substructures: subtree repeat (used in DAG compression [2; 3; 4; 5]) and tree pattern repeat (exploited in tree grammars [6; 7] and top tree compression [1]). We restrict ourselves to DAG compression of unordered rooted trees, which consists of building a Directed Acyclic Graph (DAG) that represents a tree without the redundancy of its identical subtrees (see Figure 1). Two different algorithms exist for computing the DAG reduction of a tree \(\tau\)[5] (2.2 Computing Tree Reduction), which share the same time-complexity in \(O(\#\mathcal{V}(\tau)^{2}\times\mathcal{D}(\tau)\times\log(\mathcal{D}(\tau)))\) where \(\mathcal{V}(\tau)\) denotes the set of vertices of \(\tau\) and \(\mathcal{D}(\tau)\) its outdegree. Trees that are the most compressed by DAG compression present the highest level of redundancy in their subtrees: all the subtrees of a given height are isomorphic. In this case, the DAG related to a tree \(\tau\) is linear, i.e., there exists a path going through all vertices, with exactly \(\mathcal{H}(\tau)+1\) vertices, \(\mathcal{H}(\tau)\) denoting the height of \(\tau\), which is the minimal number of vertices among trees of this height (see \(\tau_{3}\) in  
Figure 1: Trees and their DAG (Directed Acyclic Graph) reduction. In the tree, roots of isomorphic subtrees are colored identically. In the DAG, vertices are equivalence classes colored according to the class of isomorphic subtrees that they represent. Figure 1). This family of trees has been introduced in [8] as the first interesting class of trees for which the subtree isomorphism problem is in NC\({}^{2}\). It has been known under the name of nested trees [8] and next self-nested trees [5] to insist on their recursive structure and their proximity to the notion of structural self-similarity. The authors of [5] are interested in capturing the self-similarity of plants through self-nested trees. They propose to construct a self-nested tree that minimizes the distance of the original tree to the set of self-nested trees that embed the initial tree. The distance to this Nearest Embedding Self-nested Tree (NEST) is then used to quantify the self-nestedness of the tree and thus its structural self-similarity (see \(\tau\) and NEST\((\tau)\) in Figure 2). The main result of [5] (Theorem 1 and E. NEST Algorithm) is an algorithm that computes the NEST of a tree \(\tau\) from its DAG reduction in \(O(\mathcal{H}(\tau)^{2}\times\mathcal{D}(\tau))\). The goal of the present article is three-fold. We aim at proposing a new and more explicit algorithm that computes the NEST of a tree \(\tau\) with the same time-complexity \(O(\mathcal{H}(\tau)^{2}\times\mathcal{D}(\tau))\) as in [5] but that takes as input the height profile of \(\tau\) and not its DAG reduction. We establish that the height profile of a tree \(\tau\) can be computed in \(O(\#\mathcal{V}(\tau)\times\mathcal{D}(\tau))\) reducing the overall complexity of a linear factor. Based on this work, we also provide an algorithm in \(O(\mathcal{H}(\tau)^{2})\) that computes the Nearest embedded Self-nested Tree (NeST) of a tree \(\tau\) (see \(\tau\) and NeST\((\tau)\) in Figure 2). Finally, we show from numerical simulations that the distance of a tree \(\tau\) to its NeST is much lower than the distance to its NEST. The NeST is most of the time a better approximation of a tree than the NEST and thus should be privileged to quantify the degree of self-nestedness of plants. The paper is organized as follows. The structures of interest in this paper, namely unordered trees, DAG compression and self-nested trees, are defined in Section 2. Section 3 is dedicated to the definition and the study of the height profile of a tree.