# Nearest Embedded and Embedding Self-Nested Trees
## 4 Approximation Algorithms
### NeST Algorithm  
This section is devoted to the presentation of the calculation of the NeST in Algorithm 3. An illustrative example that can help the reader to follow the progress of the algorithm is provided in Section 6.  
**Proposition 7**.: _For any tree \(\tau\), Algorithm 3 returns the unique NeST of \(\tau\) in \(O(\mathcal{H}(\tau)^{2})\)._  
Proof.: The proof follows the same reasoning as the proof of Proposition 6. First, one may remark that  
\[\rho_{\text{NeST}(\tau)}(h,h-1)\leq\min\,\rho_{\tau}(h,h-1), \tag{5}\]  
because the number of subtrees of height \(h-1\) under a node \(v\) of height \(h\) can only decrease by the allowed deleting operations. Let \(v\) be a node of height \(h\) in \(\tau\) and \(\gamma_{i}(v)\) the number of subtrees of height \(i\) under \(v\). If a subtree of height \(h-i\) under \(v\) that must be deleted is not self-nested, one can first modify it to get a self-nested tree and then remove it with the same overall cost. Thus, we can assume without loss of generality that all the subtrees under \(v\) are self-nested. \(\Delta_{h-1}(v)=\gamma_{h-1}(v)-\rho_{\text{NeST}(\tau)}(h,h-1)\) denotes the number of subtrees of height \(h-1\) that have to be removed from \(v\). Let \(\gamma_{i}^{(j)}(v)\) the sequence of the modifications to obtain \(\rho_{\text{NeST}(\tau)}(h,h-1)\) subtrees of height \(h-1\) under \(v\), with \(\gamma_{i}^{(0)}(v)=\gamma_{i}(v)\). Instead of deleting a subtree of height \(h-1\), it is always less costly to decrease its height of one unit by deleting its root. However it is possible only if this internal node has only one child, i.e., if \(\rho_{\tau}(h-1,h-2)=1\) and \(\rho_{\tau}(h-1,i)=0\) for \(0\leq i<h-2\). If this new tree of height \(h-2\) must be deleted in the sequel, it will be done with the same global cost as by directly deleting the subtree of height \(h-1\). Consequently,  
\[\left\{\begin{array}{rcl}\gamma_{h-1}^{(1)}(v)&=&\rho_{\text{NeST}(\tau)}(h, h-1),\\ \gamma_{h-2}^{(1)}(v)&=&\gamma_{h-2}^{(0)}(v)+\Delta_{h-1}(v)\mathbb{I}_{\{ \rho_{\tau}(h-1,h-2)=1,\,\forall\,3\leq i\leq h,\,\rho_{\tau}(h-1,h-i)=0\}}. \end{array}\right.\]  
From now on, the number of subtrees of height \(h-2\) under \(v\) will thus not increase and we obtain  
\[\rho_{\text{NeST}(\tau)}(h,h-2)\leq\min_{\{v\in\mathcal{V}(\tau)\,:\,\mathcal{ H}(\tau[v])=h\}}\,\gamma_{h-2}^{(1)}(v).\]  
There are \(\Delta_{h-2}(v)=\gamma_{h-2}^{(1)}(v)-\rho_{\text{NeST}(\tau)}(h,h-2)\) subtrees of height \(h-2\) to be deleted under \(v\). We can repeat the previous reasoning and delete the root of subtrees of height \(h-2\) if possible rather than delete the whole structure, and so on for any height. Thus, the sequence \(\gamma_{i}^{(j)}\) is defined from  
\[\left\{\begin{array}{rcl}\Delta_{h-1-i}(v)&=&\gamma_{h-1-i}^{(i)}(v)-\rho_{ \text{NeST}(\tau)}(h,h-1-i),\\ \gamma_{h-1-i}^{(i+1)}(v)&=&\rho_{\text{NeST}(\tau)}(h,h-1-i),\\ \gamma_{h-2-i}^{(i+1)}(v)&=&\gamma_{h-2-i}^{(i)}(v)+\Delta_{h-1-i}(v)\mathbb{I }_{\{\rho_{\tau}(h-1,h-2)=1,\,\forall\,i+2\leq j\leq h,\,\rho_{\tau}(h-i,h-j)= 0\}},\end{array}\right.\]and we have  
\[\forall\,0\leq i\leq h-2,\;\rho_{\text{NeST}(\tau}(h,h-2-i)\leq\min_{\{\
u\in \mathcal{V}(\tau)\,:\,\mathcal{H}(\tau[v])=h\}}\;\gamma_{h-2-i}^{(i+1)}(v). \tag{6}\]  
The tree returned by Algorithm 3 saturates the inequalities (5) and (6) for all the possible values of \(h\) and \(i\). Decreasing of one unit the height profile at \((h_{1},h_{2})\) has a (strictly) positive cost. Thus, this tree is the (unique) NeST of \(\tau\). The time-complexity is given by the size of the height profile array.