# A Linear-Time Algorithm for the Isometric Reconciliation of Unrooted Trees
## 2 Algorithm
### Checking Distances  
In the third phase of the algorithm, we are given a set of potential roots, and we need to verify whether they correspond to actual reconciliations. We do so based on comparing distances between pairs of selected leaves in trees \(S\) and \(G\), as explained in the following two claims. Note that the definition of isometric reconciliation requires that distances between a node of \(G\) and its descendants and ancestors are preserved by the mapping. However, for other pairs of nodes, the distance in \(G\) can be greater than the distance of the corresponding points in \(S\). For example, in Figure 2 leaves \(a_{1}\) and \(b_{1}\) of \(G\) are at distance 8, but the corresponding leaves \(a\) and \(b\) from \(S\) have a distance of only 4. Next we show that the distances in \(G\) cannot be smaller than distances in \(S\). **Claim 5**: _Let \((G_{O},S_{O},\Phi)\) be an isometric reconciliation of a triple \((G,S,\mu)\), where trees \(S\) and \(G\) can be either rooted or unrooted. Then for each two nodes \(u\) and \(v\) from \(G\), we have \(d_{G}(u,v)\geq d_{S}(\Phi(u),\Phi(v))\)._  
Proof. : Note that the definition of isometric reconciliation implies that if \(u\) is an ancestor of \(v\) in \(G\); then \(\Phi(u)\) is an ancestor of \(\Phi(v)\) and \(d_{G_{O}}(u,v)=d_{S_{O}}(\Phi(u),\Phi(v))\). Additionally, note that for any nodes \(u\) and \(v\) of \(G\) we have \(d_{G}(u,v)=d_{G_{O}}(u,v)\), and similarly, the distances remain preserved between \(S\) and \(S_{O}\). Let \(w=\mathsf{lca}_{G_{O}}(u,v)\) and \(x=\mathsf{lca}_{S_{O}}(\[PERSON](u),\[PERSON](v))\). Note that \(\[PERSON](w)\) must be an ancestor of \(x\), because it is an ancestor of both \(\[PERSON](u)\) and \(\[PERSON](v)\).  
\[d_{G}(u,v) = d_{G_{O}}(w,u)+d_{G_{O}}(w,v)\] \[= d_{S_{O}}(\[PERSON](w),\[PERSON](u))+d_{S_{O}}(\[PERSON](w),\[PERSON](v))\] \[\geq d_{S_{O}}(x,\[PERSON](u))+d_{S_{O}}(x,\[PERSON](v))\] \[= d_{S_{O}}(\[PERSON](u),\[PERSON](v))\] \[= d_{S}(\[PERSON](u),\[PERSON](v))\]Given a rooted tree \(T\), let \(\ell_{T}\) be the mapping which maps each node \(x\) of \(T\) to the smallest leaf in the subtree of \(T\) rooted at \(x\) under some fixed complete order on the set \(L(T)\). **Claim 6**. : _Let \(S\) be a rooted tree and \(G\) an unrooted tree. Trees \(S\) and \(G\) can be reconciled if and only if the following two conditions hold:_  
* _There is a potential rooting_ \((q,h)\) _of_ \(G\) _(let_ \(G^{\prime}\) _be_ \(G\) _rooted in_ \(q\)_)_
* _For each two nodes_ \(v_{1}\) _and_ \(v_{2}\) _which are in_ \(G^{\prime}\) _children of the same node we have_ \[d_{G^{\prime}}(\ell_{G^{\prime}}(v_{1}),\ell_{G^{\prime}}(v_{2}))\geq d_{S}( \ell_{G^{\prime}}(v_{1}),\ell_{G^{\prime}}(v_{2})).\] (8)  
Note that Equation (8) uses the assumption that the leaves are shared between \(G\), \(G^{\prime}\) and \(S\). Proof. : If the reconciliation \((G_{O},S_{O},\Phi)\) exists, we can obtain the potential rooting \((q,h)\) by taking the root of \(G_{O}\) as \(q\) and setting \(h=d_{S_{O}}(\Phi(q),r)\) where \(r\) is the root of tree \(S\). Inequality (8) is implied by Claim 5. Let us now assume the existence of a potential rooting \((q,h)\) satisfying the two conditions. We will root tree \(G\) in \(q\) and construct the mapping \(\Phi\) as follows. Node \(q\) is mapped to the point located in distance \(h\) above the root of \(S\); let us call this point \(r\) and denote tree \(S\) extended with \(r\) as \(S^{\prime}\). Each node \(v\) of the rooted \(G^{\prime}\) is then mapped to \(\Phi(v)=S^{\prime}(r,\ell_{G^{\prime}}(v),d_{G^{\prime}}(q,v))\). First of all, we need to prove that this mapping exists, in particular that \(d_{G^{\prime}}(q,v)\leq d_{S^{\prime}}(r,\ell_{G^{\prime}}(v))\). This is true because the definition of a potential rooting implies that \(d_{S^{\prime}}(r,\ell_{G^{\prime}}(v))=d_{G^{\prime}}(q,\ell_{G^{\prime}}(v))\), and since the path from \(q\) to \(\ell_{G^{\prime}}(v)\) passes through \(v\), we have the desired inequality.