# A Linear-Time Algorithm for the Isometric Reconciliation of Unrooted Trees
## 2 Algorithm
### Checking Distances
Note that the leaves of \(G^{\prime}\) are correctly mapped by \(\Phi\) to their counterparts in \(S^{\prime}\). Next we prove that if \(v\) is an ancestor of \(w\) in \(G^{\prime}\) and \(\Phi(v)\) is an ancestor of \(\Phi(w)\) in \(S^{\prime}\), then \(d_{G}(v,w)=d_{S}(\Phi(v),\Phi(w))\). Based on the ancestor relationships, the path from \(w\) to \(q\) passes through \(v\) and the path from \(\Phi(w)\) to \(r\) passes through \(\Phi(v)\), and therefore, \(d_{G^{\prime}}(w,q)=d_{G^{\prime}}(w,v)+d_{G^{\prime}}(v,q)\) and \(d_{S^{\prime}}(\[PERSON](w),r)=d_{S^{\prime}}(\[PERSON](w),\[PERSON](v))+d_{S^{\prime}}(\Phi (v),r)\). Based on the definition of \(\Phi\), \(d_{G^{\prime}}(w,q)=d_{S^{\prime}}(\[PERSON](w),r)\) and \(d_{G^{\prime}}(v,q)=d_{S^{\prime}}(\[PERSON](v),r)\). These equations imply the desired result. Finally, we need to prove that if \(v\) is the parent of \(w\) in \(G^{\prime}\) then \(\[PERSON](v)\) is an ancestor of \(\[PERSON](w)\) in \(S^{\prime}\). Let \(a_{w}=\ell_{G^{\prime}}(w)\) and \(a_{v}=\ell_{G^{\prime}}(v)\). If \(a_{w}=a_{v}\), both \(\Phi(v)\) and \(\[PERSON](w)\) are on the path from \(r\) to \(a_{w}\), and by comparing their distances from the root, we see that \(\[PERSON](v)\) must be an ancestor of \(\[PERSON](w)\). If \(a_{w}\
eq a_{v}\), let \(w^{\prime}\) be the child of \(v\) on the path to \(a_{v}\). Then \(\ell_{G^{\prime}}(w^{\prime})=a_{v}\), and \(w\) and \(w^{\prime}\) are two children of the same node of \(G^{\prime}\). Therefore, we can apply Inequality (8) to obtain \(d_{G^{\prime}}(a_{v},a_{w})\geq d_{S^{\prime}}(a_{v},a_{w})\). Note that \(v=\mathsf{lca}_{G^{\prime}}(a_{v},a_{w})\) and thus \(d_{G^{\prime}}(a_{v},a_{w})=d_{G^{\prime}}(a_{v},q)+d_{G^{\prime}}(a_{w},q)- 2d_{G^{\prime}}(q,v)\). Similarly in \(S^{\prime}\), let \(x=\mathsf{lca}_{S^{\prime}}(a_{v},a_{w})\); then \(d_{S^{\prime}}(a_{v},a_{w})=d_{S^{\prime}}(a_{v},r)+d_{S^{\prime}}(a_{w},r)- 2d_{S^{\prime}}(r,x)\). By combining these three facts, we get the inequality \(d_{G^{\prime}}(v,q)\leq d_{S^{\prime}}(x,r)\). As \(\Phi(q)=r\) and \(r\) is an ancestor of \(\Phi(v)\), we have that \(d_{G^{\prime}}(v,q)=d_{S^{\prime}}(\Phi(v),r)\). Therefore, we see that the depth of \(\Phi(v)\) in \(S^{\prime}\) is smaller or equal to the depth of \(x\). Both \(x\) and \(\Phi(v)\) are ancestors of \(a_{v}\), which implies that \(\Phi(v)\) must be an ancestor of \(x\) (which includes the possibility that \(\Phi(v)=x\)). This in turn implies that \(\Phi(v)\) must be also an ancestor of \(a_{w}\). Again, since both \(\Phi(v)\) and \(\Phi(w)\) are ancestors of \(a_{w}\) and \(\Phi(w)\) is in a greater depth than \(\Phi(v)\), it must be a descendant of \(\Phi(v)\). Claim 5 shows that given unrooted input trees \(G\) and \(S\), we can check any pair of leaves \(a\) and \(b\) and if \(d_{G}(a,b)<d_{S}(a,b)\), then no reconciliation of these trees exists. Claim 6 shows that for a fixed potential root in \(S\), it is sufficient to check distances between \(O(N)\) pairs of leaves to verify that the potential rooting corresponds to a valid reconciliation. However, we would like to verify all potential roots of \(S\) in \(O(N)\) total time. For every rooted subtree \(\mathsf{sub}(G,v,u)\) of \(G\), we can find its smallest leaf; this leaf will correspond to \(\ell_{G^{\prime}}(v)\) for all rooted versions \(G^{\prime}\) of \(G\) in which this rooted subtree appears as one of the subtrees. These smallest leaves can be easily computed in \(O(N)\) using the bottom-up ordering of rooted subtrees of \(G\). Then, given any node \(u\) of \(G\), we take all pairs of its neighbors \(v_{1}\) and \(v_{2}\), take the smallest leaves \(a_{1}\) and \(a_{2}\) in the subtrees \(\sub(G,v_{1},u)\) and \(\sub(G,v_{2},u)\) and check whether \(d_{G}(a_{1},a_{2})\geq d_{S}(a_{1},a_{2})\). Provided that tree \(G\) has at least one internal node, these checks cover all pairs of leaves \(\ell_{G^{\prime}}(v_{1})\) and \(\ell_{G^{\prime}}(v_{2})\) from Claim 6 that can occur for any root location in \(S\).