# Nearest Embedded and Embedding Self-Nested Trees
## 4 Approximation Algorithms
### Definitions
#### 4.1.2 Constrained Editing Operations  
[PERSON]'s edit distance is defined from the above editing operations and from constrained mappings between trees [11] (3.1 Constrained Edit Distance Mappings). A constrained mapping between two trees \(\tau\) and \(\theta\) is a mapping [11] (2.3.2 Editing Distance Mappings), i.e., a one-to-one correspondence \(\varphi\) from a subset of \(\mathcal{V}(\tau)\) into a subset of \(\mathcal{V}(\theta)\) preserving the ancestor order, with an additional condition on the Least Common Ancestors (LCAs) [11] (condition (2) p. 208): if, for \(1\leq i\leq 3\), \(v_{i}\in\mathcal{V}(\tau)\) and \(w_{i}=\varphi(v_{i})\in\mathcal{V}(\theta)\), then \(\text{LCA}(v_{1},v_{2})\) is a proper ancestor of \(v_{3}\) if and only if \(\text{LCA}(w_{1},w_{2})\) is a proper ancestor of \(w_{3}\). Let \(\theta\) be a tree that approximates \(\tau\) obtained by inserting nodes in \(\tau\) only and consider the induced mapping \(M_{\tau\to\theta}\) that associates nodes of \(\tau\) with themselves in \(\theta\). We want the approximation process  
Figure 4: Inserting a node. Figure 3: Deleting a node. to be consistent with [PERSON]'s edit distance \(D_{Z}\), i.e., we want the mapping \(M_{\tau\to\theta}\) to be a constrained mapping in the sense of [PERSON], which in particular implies \(D_{Z}(\theta,\tau)=\#\mathcal{V}(\theta)-\#\mathcal{V}(\tau)\). We shall prove that this requirement excludes some inserting operations in our context. Indeed, the mapping \(M_{\tau\to\theta}\) involved in the inserting operation of Figure 4 is partially displayed in Figure 5, nodes \(v_{i}\) of \(\tau\) being associated with nodes \(w_{i}\) of \(\theta\). The LCA of \(v_{1}\) and \(v_{2}\) in \(\tau\) is a proper ancestor of \(v_{3}\). However, the LCA of \(w_{1}\) and \(w_{2}\) in \(\theta\) is not a proper ancestor of \(w_{3}\). Consequently, this mapping is not a constrained mapping as defined by [PERSON]. A necessary and sufficient condition for \(M_{\tau\to\theta}\) to be a constrained mapping is given in Lemma 2. **Lemma 2**. : _Let \(\tau\) be a tree and \(v\in\mathcal{V}(\tau)\). Let \(\theta\) be the tree obtained from \(\tau\) by adding a node \(w\) as a child of \(v\) making the nodes of the subset \(C\subset\mathcal{C}_{\tau}(v)\) children of \(w\). The mapping \(M_{\tau\to\theta}\) induced by these inserting operations is a constrained mapping in the sense of Zhang if and only if \(C=\emptyset\), \(\#C=1\) or \(\#C=\#\mathcal{C}_{\tau}(v)\)._  
Proof. : The proof is obvious if \(v\) has one or two children. Thus, we assume that \(v\) has at least three children \(c_{1}\), \(c_{2}\) and \(c_{3}\). In \(\tau\), the LCA of \(c_{1}\) and \(c_{2}\) is \(v\) and \(v\) is an ancestor of \(c_{3}\). Adding \(w\) as the parent of \(c_{1}\) and \(c_{2}\) makes it the LCA of these two nodes, but not an ancestor of \(c_{3}\) in \(\theta\). The additional condition on the LCAs is then not satisfied. This problem appears only when making \(w\) the parent of at least two children and of not all the children of \(v\). Consequently, we restrict ourselves to the following inserting operations which are the only ones that ensure that the associated mapping satisfies [PERSON]'s condition: adding \(w\) as a child of \(v\) will make \(w\) (i) a leaf, (ii) the parent of one current child of \(v\), or (iii) the parent of all the current children of \(v\). However, it should be noticed that (iii) can always be expressed as (ii) (see Figure 6). Finally, we only consider the inserting operations that make the new child of \(v\) the parent of zero or one current child of \(v\). For obvious reasons of symmetry, the allowed deleting operations are the complement of inserting operations, i.e., one can delete an internal node if and only if it has a unique child, which also ensures that the induced mapping is constrained in the sense of [PERSON]. Figure 5: The tree \(\theta\) is obtained from \(\tau\) by inserting an internal node.