# Nearest Embedded and Embedding Self-Nested Trees
## 4 Approximation Algorithms
### NEST Algorithm  
To present our NEST algorithm in a concise form in Algorithm 2, we need to define the following operations involving two vectors \(u\) and \(v\) of the same size \(n\) and a real number \(\gamma\),  
\[\left\{ \begin{array}{ccccc}u&+&v&=&(u_{1}+v_{1}\,,\,\ldots\,,\,u_{n}+v_{n}),\\ u&+&\gamma&=&(u_{1}+\gamma\,,\,\ldots\,,\,u_{n}+\gamma),\\ u&\vee&\gamma&=&(\max(u_{1},\gamma)\,,\,\ldots\,,\,\max(u_{n},\gamma)).\end{array} \right.\]  
In other words, these operations must be understood component by component. In addition, in a condition, \(u=0\) (\(u\
eq 0\), respectively) means that for all \(1\leq i\leq n\), \(u_{i}=0\) (\(u_{i}\
eq 0\), respectively). Finally, for \(1\leq i\leq j\leq n\), \(u_{i\ldots j}\) denotes the vector \((u_{i},\ldots,u_{j})\) of length \(j-i+1\). This notation will also  
Figure 8: Allowed (\(\gamma\)) and forbidden (\(\mathbf{\
u}\)) deleting operations to construct the NeST of a tree. Figure 7: Allowed (\(\mathbf{\
u}\)) and forbidden (\(\mathbf{\chi}\)) inserting operations to construct the NEST of a tree. be used in Algorithm 3 for calculating the NeST. It should be noticed that an illustrative example that can help the reader to follow the progress of the algorithm is provided in Section 6. ```
1 FunctionNEST(\(\tau\)): Data: the height profile \(\rho\) of an unordered tree \(\tau\) Result: the nearest embedding self-nested tree of \(\tau\) for\(h_{1}\)from \(1\)to\(\mathcal{H}(\tau)\)do
2 for\(h_{2}\)from\(h_{1}-1\)to\(0\)do
3\(\Delta\leftarrow\max\,\rho_{h_{1},h_{2}}-\rho_{h_{1},h_{2}}\)
4\(\rho_{h_{1},h_{2}}\leftarrow\max\rho_{h_{1},h_{2}}\)
5\(i\gets 1\)while\(\Delta\
eq 0\)and\(i\leq h_{2}\)do
6\(\Delta\), \(\rho_{h_{1},h_{2}-i}\leftarrow(\Delta-\rho_{h_{1},h_{2}-i})\lor 0\), \(\rho_{h_{1},h_{2}-i}-\Delta\)
7\(i\gets i+1\)
8
9 returnSN(\(\rho\))
```  
**Algorithm 2**Construction of the nearest embedding self-nested tree. The relation between the above algorithm and the NEST of a tree is provided in the following result, which states in particular the existence of the NEST. Proposition 6: _For any tree \(\tau\), Algorithm 2 returns the unique NEST of \(\tau\) in \(O(\mathcal{H}(\tau)^{2}\times\mathcal{D}(\tau))\)._  
Proof: By definition of the NEST, the height of all the pre-existing nodes of \(\tau\) cannot be modified. Thus, the number of nodes of height \(h-1\) under a node of height \(h\) can only increase by inserting subtrees in the structure. Then we have  
\[\rho_{\text{NEST}(\tau)}(h,h-1)\geq\max\,\rho_{\tau}(h,h-1). \tag{3}\]  
Let \(v\) be a vertex of height \(h\) in \(\tau\). We recall that \(\gamma_{i}(v)\) denotes the number of subtrees of height \(i\) under \(v\). Our objective is to understand the consequences for \(\gamma_{i}(v)\) of inserting operations to obtain \(\rho_{\text{NEST}(\tau)}(h,h-1)\) subtrees of height \(h-1\) under \(v\). To this aim, we shall define a sequence \(\gamma_{i}^{(h-1,j)}(v)\) starting from \(\gamma_{i}^{(h-1,0)}(v)=\gamma_{i}(v)\) that corresponds to the modified versions of \(\tau\). The first exponent \(h-1\) means that this sequence concerns editing operations used to get the good number of subtrees of height \(h-1\) under \(v\). Let \(\Delta_{h-1}^{(0)}(v)=\rho_{\text{NEST}(\tau)}(h,h-1)-\gamma_{h-1}^{(0)}(v)\) be the number of subtrees of height \(h-1\) that must be added under \(v\) to obtain the height profile of the NEST under \(v\), i.e.,  
\[\gamma_{h-1}^{(h-1,1)}(v)=\rho_{\text{NEST}(\tau)}(h,h-1).\]  
Implicitly, it means that \(\gamma_{i}^{(h-1,1)}(v)=\gamma_{i}(0)(v)\) for \(i\
eq h-1\). The subtrees of height \(h-1\) that we must add are isomorphic, self-nested and embed all the subtrees of height \(h-2\) appearing in \(\tau\) by definition of the NEST. In particular, they can be obtained by the allowed inserting operations from the subtrees of height \(h-2\) under \(v\), by first adding an internal node to increase their height to \(h-1\).