# Nearest Embedded and Embedding Self-Nested Trees
## 4 Approximation Algorithms
### Definitions
#### 4.1.3. Preserving the Height of the Pre-Existing Nodes  
In [5] (Definition 9 and Figure 6), the NEST of a tree \(\tau\) is obtained by successive partial linearizations of the (non-linear) DAG of \(\tau\) which consist of merging all the nodes at the same height of the DAG. A consequence is that the height of any pre-existing node of \(\tau\) is not changed by the inserting operations. For the sake of consistency with [5], we only consider inserting and deleting operations that preserve the height of all the pre-existing nodes of \(\tau\).  
The next two results deal with inserting operations that preserve the height of the pre-existing nodes.  
**Lemma 3**: _Let \(\tau\) be a tree, \(v\in\mathcal{V}(\tau)\) and \(c\in\mathcal{C}_{\tau}(v)\). Let \(\theta\) be the tree obtained from \(\tau\) by adding the internal node \(w\) as a child of \(v\) making \(w\) the parent of \(c\). Then,_  
\[\forall\,u\in\mathcal{V}(\tau),\ \mathcal{H}(\theta[u])=\mathcal{H}(\tau[u]) \quad\Longleftrightarrow\quad\mathcal{H}(\tau[c])+1<\mathcal{H}(\tau[v]).\]  
Adding \(w\) may only increase the height of \(v\) and the one of its ancestors in \(\tau\). If the height of \(v\) is not changed by adding \(w\), the height of its ancestors will not be modified. The height of \(v\) remains unchanged if and only if the height of \(w\) in \(\theta\), i.e., \(\mathcal{H}(\tau[c])+1\), is strictly less than the height of \(\tau[v]\).  
**Lemma 4**: _Let \(\tau\) be a tree and \(v\in\mathcal{V}(\tau)\). Let \(\theta\) be the tree obtained from \(\tau\) by adding a tree \(t\) as a child of \(v\). Then,_  
\[\forall\,u\in\mathcal{V}(\tau),\ \mathcal{H}(\theta[u])=\mathcal{H}(\tau[u]) \quad\Longleftrightarrow\quad\mathcal{H}(t)+1\leq\mathcal{H}(\tau[v]).\]  
Adding a subtree \(t\) under \(v\) may only increase the height of \(v\) and the one of its ancestors in \(\tau\). If the height of \(v\) is not changed by adding \(t\), the height of its ancestors will not be modified. Adding \(t\) will make the height of \(v\) increase if \(\mathcal{H}(t)\) is strictly greater than the height of the higher child of \(v\).  
A particular case of Lemma 4 is the insertion of leaves in a tree. Considering the above result, a leaf can be added under \(v\) if and only if \(\mathcal{H}(\tau[v])\geq 1\), i.e., \(v\) is not a leaf. The below results concern deleting operations that preserve the height of the remaining nodes of \(\tau\).  
**Lemma 5**: _Let \(\tau\) be a tree, \(v\in\mathcal{V}(\tau)\), \(w\in\mathcal{C}_{\tau}(v)\) and \(\mathcal{C}_{\tau}(w)=\{c\}\). Let \(\theta\) be the tree obtained from \(\tau\) by deleting the internal node \(w\) making its unique child \(c\) a child of \(v\). Then,_  
\[\forall\,u\in\mathcal{V}(\theta),\ \mathcal{H}(\theta[u])=\mathcal{H}(\tau[u]) \quad\Longleftrightarrow\quad\exists\,w^{\prime}\in\mathcal{C}_{\tau}(v) \setminus\{w\},\ \mathcal{H}(\tau[w^{\prime}])+1=\mathcal{H}(\tau[v]).\]  
Deleting \(w\) may only decrease the height of \(v\) and the one of its ancestors in \(\tau\). If the height of \(v\) is not changed by deleting \(w\), the height of its ancestors will not be modified. The height of \(v\) remains unchanged if and only if it has a child different of \(w\) of height \(\mathcal{H}(\tau[v])-1\).  
**Lemma 6**: _Let \(\tau\) be a tree, \(v\in\mathcal{V}(\tau)\), \(c\in\mathcal{C}_{\tau}(v)\). Let \(\theta\) be the tree obtained from \(\tau\) by deleting the subtree \(\tau[c]\). Then,_  
\[\forall\,u\in\mathcal{V}(\theta),\ \mathcal{H}(\theta[u])=\mathcal{H}(\tau[u]) \quad\Longleftrightarrow\quad\exists\,c^{\prime}\in\mathcal{C}_{\tau}(v) \setminus\{c\},\ \mathcal{H}(\tau[c^{\prime}])+1=\mathcal{H}(\tau[v]).\]  
The proof follows the same reasoning as in the previous result.