# A Linear-Time Algorithm for the Isometric Reconciliation of Unrooted Trees
## 2 Algorithm
### Final Output and Possible Solution Sets
These points all share the same value of \(h\) and their counterparts form an interval on some path in \(G\) of the same length as the interval in \(S\). Consider now the case when \(r_{1}\) and \(r_{2}\) are not on the same edge. Let \(x_{1},\ldots,x_{z}\) be the path in \(S\) such that \(r_{1}\) is on the edge \(\{x_{1},x_{2}\}\), and \(r_{2}\) is on the edge \(\{x_{z-1},x_{z}\}\) (refer to Figure 6). All leaves can be partitioned into three classes: let \(A_{1}\) be the set of leaves \(a\) such that \(\text{between}_{S}(a,x_{1},x_{z})\) is true, \(A_{2}\) be the set of leaves such that \(\text{between}_{S}(a,x_{z},x_{1})\) is true and \(B\) be the remaining leaves. Let \(A=A_{1}\cup A_{2}\). Consider now trees \(S_{A}\) and \(G_{A}\). Nodes \(x_{2},\ldots,x_{z-1}\) all have degree two in \(S_{A}\), and thus we can replace path \(x_{1},\ldots,x_{z}\) by a single edge in \(S_{A}\). We can apply Claim 7 to \(S^{(1)}\) and \(S^{(2)}\) to see that points \(r_{1}\) and \(r_{2}\) must be potential roots in \(S_{A}\) as well (see Figure 7). Since \(r_{1}\) and \(r_{2}\) are on a single edge in \(S_{A}\), all four statements of this claim hold for \(r_{1}\), \(r_{2}\) and \(r_{3}\) in trees \(G_{A}\) and \(S_{A}\). Let \((q^{\prime}_{i},h^{\prime}_{i})\) be the potential rooting of \(G_{A}\) with respect to \(S^{(i)}_{A}\) for \(i\in\{1,2,3\}\). We thus have that \((q^{\prime}_{3},h^{\prime}_{3})\) exists as a potential rooting of \(G_{A}\) with respect to \(S^{(3)}\); it is located on the path between \(q^{\prime}_{1}\) and \(q^{\prime}_{2}\), \(d_{S}(r_{1},r_{2})=d_{G}(q^{\prime}_{1},q^{\prime}_{2})\), and \(h^{\prime}_{1}=h^{\prime}_{2}\). From now on we will denote the common value \(h^{\prime}_{1}=h^{\prime}_{2}\) as \(h\). We also have that \(h^{\prime}_{3}=h\) because \(r_{1}\), \(r_{2}\) and \(r_{3}\) are all on the same edge of \(S_{A}\). Figure 6: The path containing \(r_{1}\), \(r_{2}\) and \(r_{3}\) in tree \(S\). Leaves are partitioned into sets \(A_{1}\), \(A_{2}\) and \(B\), where \(B\) is in the figure represented by the union \(B_{1}\cup B_{2}\cup\cdots\cup B_{k}\). Next we prove that \(q_{1}=q_{1}^{\prime}\) and \(q_{2}=q_{2}^{\prime}\). According to Claim 7, \(q_{1}^{\prime}\) is the closest point in \(G_{A}\) to \(q_{1}\). Consider now the path from \(q_{1}\) to \(q_{2}^{\prime}\), and note that \(q_{2}^{\prime}\) is in \(G_{A}\). The point where this path first enters \(G_{A}\) must be \(q_{1}\). Symmetrically, \(q_{2}^{\prime}\) must be on the path from \(q_{2}\) to \(q_{1}^{\prime}\). This implies that the points \(q_{1},q_{1}^{\prime},q_{2}^{\prime},q_{2}\) are on a single path in \(G\) in this order, although some adjacent points may coincide. Let us now assume that \(q_{1}\
eq q_{1}^{\prime}\), and thus \(q_{1}\) is not in \(G_{A}\). Then there must be a leaf \(b\in B\) such that \(q_{1}\) is on the path from \(b\) to \(q_{1}^{\prime}\). For \(i\in\{1,2\}\) we have that \(h=h_{i}^{\prime}=h_{i}-d_{G}(q_{i},q_{i}^{\prime})\) by Claim 7. Since \(r_{i}\in\mathcal{R}\), we have \(d_{G}(b,q_{i})=d_{S}(b,r_{i})+h_{i}\). Combining these two facts, we get  
\[d_{G}(b,q_{i})=d_{S}(b,r_{i})+h+d_{G}(q_{i},q_{i}^{\prime}). \tag{10}\]  
In addition,  
\[d_{G}(b,q_{2}) = d_{G}(b,q_{1})+d_{G}(q_{1},q_{1}^{\prime})+d_{G}(q_{1}^{\prime}, q_{2}^{\prime})+d_{G}(q_{2}^{\prime},q_{2}) \tag{11}\] \[= (d_{S}(b,r_{1})+h+d_{G}(q_{1},q_{1}^{\prime}))+d_{G}(q_{1},q_{1}^ {\prime})+d_{S}(r_{1},r_{2})+d_{G}(q_{2}^{\prime},q_{2}). \tag{12}\]  
By combining the right-hand side of Equation (10) for \(i=2\) and the right-hand side of Equation (12), we get  
\[d_{S}(b,r_{2})-(d_{S}(b,r_{1})+d_{S}(r_{1},r_{2}))=2d_{G}(q_{1},q_{1}^{\prime}).\]  
The left-hand side of this equation is at most \(0\) due to triangle inequality, and therefore, the right-hand side must be zero, which is a contradiction with our assumption that \(q_{1}\) is not in \(G_{A}\). Therefore, we have that \(q_{1}=q_{1}^{\prime}\) and analogously \(q_{2}=q_{2}^{\prime}\).