# A Linear-Time Algorithm for the Isometric Reconciliation of Unrooted Trees
## 2 Algorithm
### Potential Roots of an Unrooted Species Tree  
Once we have potential rootings computed for all rooted subtrees of an unrooted tree \(S\), we can consider potential roots of \(S\), defined as follows. Definition 2: Let \(G\) and \(S\) be unrooted. A point \(r\) in \(S\) is called a potential root of \(S\) if there exists some potential rooting \((q,u)\) of \(G\) with respect to \(S\) rooted at \(r\). For each edge \(\{x_{1},x_{2}\}\) of \(S\), consider rooting tree \(S\) at the point \(r=S(x_{1},x_{2},\alpha)\) for \(0\leq\alpha\leq d_{S}(x_{1},x_{2})\). This yields a rooted tree \(S^{\prime}_{\alpha}\) on which we can apply Claim 4, using precomputed potential rootings \((q_{1},h_{1})\) and \((q_{2},h_{2})\) for the two subtrees \(S_{1}\) and \(S_{2}\) of \(S\) rooted at \(x_{1}\) and \(x_{2}\). Using this claim, we can compute for which values of \(\alpha\) we obtain a potential rooting of \(G\) with respect to \(S^{\prime}_{\alpha}\). Figure 4: Construction of representative set \(A\) for \(q\) from representative sets \(A_{1}=\{a_{1},\ldots,a_{g}\}\) and \(A_{2}=\{b_{1},\ldots,b_{h}\}\). The algorithm in the text considers three different cases depicted from left to right. Construction of set \(A\) involves some arbitrary choices; for example, in the first case, \(a_{3}\) can be replaced in \(A\) by \(b_{2}\). Figure 5: Illustration of the algorithm for checking Condition 3 when \(q\
eq q_{i}\). We need to check that the path connecting \(q_{i}\) and \(q_{j}\) is outside \(G_{L(S_{i})}\) except for \(q_{i}\). For each leaf \(a\) from the representative set \(A_{i}\) of \(q_{i}\), we check that \(\mathsf{between}_{G}(a,q_{i},q_{j})\) is true. Left: \(\mathsf{between}_{G}(a,q_{i},q_{j})\) is true; right: \(\mathsf{between}_{G}(a,q_{i},q_{j})\) is false, \(u\in G_{L(S_{i})}\). In particular, Condition 1 of Claim 4 specifies the value of \(h\) which does not depend on the unknown distance \(\alpha=d_{S}(x,r)\). Condition 2 specifies the position \(q\) of the root in \(G\), but for this position to be valid, value of \(\beta=h-h_{1}+\alpha\) must be from the specified interval. This translates to interval \([h_{1}-h,h_{1}-h+d_{G}(q_{1},q_{2})]\) for \(\alpha\). Possible values of \(\alpha\) also must be within edge \(\{x_{1},x_{2}\}\), and thus we take an intersection of two intervals, yielding the following interval of possible values:  
\[\alpha\in[\max(0,h_{1}-h),\min(d_{S}(x_{1},x_{2}),h_{1}-h+d_{G}(q_{1},q_{2}))].\]  
Note that this interval might be empty, signifying that no potential rooting exists, or it might contain only a single value of \(\alpha\). Finally, to satisfy Condition 3 of Claim 4 for \(i\in\{1,2\}\), we consider two cases. If the path \(\pi\) connecting \(q_{1}\) and \(q_{2}\) lies outside of \(G_{L(G_{i})}\) except for the endpoints, we can place point \(q\) anywhere on this path without violating this condition. However, if some portion of this path is inside \(G_{L(G_{i})}\) for some \(i\in\{1,2\}\), we have to place \(q\) to \(q_{i}\), restricting possible values of \(\beta\) to a single value (0 or \(d_{G}(q_{1},q_{2})\), depending on \(i\)), and thus \(\alpha\) is also restricted to a single value or potentially to an empty set. Condition 3 has to be satisfied for both values of \(i\in\{1,2\}\). To algorithmically check whether \(\pi\) is outside of \(G_{L(G_{i})}\), we again use the set \(A_{i}\) of representative leaves for \(q_{i}\). For each leaf \(a\in A_{i}\), we evaluate the predicate \(\mathsf{between}_{G}(a,q_{i},q_{j})\), where \(j\) is the index from \(\{1,2\}\) different from \(i\). If the predicate is true for all representative leaves, the path is outside. The result of this phase of the algorithm is for every edge \(\{x_{1},x_{2}\}\) of \(S\) an interval of potential roots of \(S\) which yield potential rootings of \(G\). The location of the root \(q\) is given in the form \(G(a,b,f(\alpha))\) where \(\alpha\) is the distance of the root of \(S\) from node \(x_{1}\) and \(f\) is a function of the form \(f(\alpha)=\alpha+d\), where \(d=h-h_{1}\) as discussed above.