## 4 Algorithms for Tree Compatibility and Incomplete Directed Perfect Phylogeny
### Tree Compatibility
It can be shown that if \(S\) is empty, then \(\mathcal{P}\) is incompatible [10]. This case is handled in Lines 6-7. If \(S\) is not empty, the algorithm creates a tentative root \(r_{U}\) labeled by \(S\) for the tree \(\mathcal{T}_{U}\) for \(\text{Desc}_{\mathcal{P}}(U)\) and links \(r_{U}\) to its parent (Line 8). If \(S\) consists of exactly one element that is a leaf in \(H_{\mathcal{P}}\), then \(r_{U}\) is a potential leaf in the output tree \(\mathcal{T}\). We set the label of \(r_{U}\) appropriately, skip the rest of the current iteration of the **while** loop, and **continue** to the next iteration (Lines 9-11). Line 12 replaces \(U\) by its successor with respect to \(S\). Lines 14-15 enqueue each of \(U|W_{1},U|W_{2},\ldots,U|W_{p}\)--where \(U|W_{j}\) denotes the position \((U(1)\cap W_{j},\ldots,U(k)\cap W_{j})\)--along with \(r_{U}\), for processing in subsequent iterations. If the **while** loop terminates without detecting incompatibility, BuildNT returns the phylogenetic \(X\)-tree \(\mathcal{T}=(T,\phi)\), where \(T\) is the tree with root \(r_{U_{\text{root}}}\) and \(\phi\) is the labeling function constructed in Line 10. ```
Input: A profile \(\mathcal{P}=\{\mathcal{T}_{1},\ldots,\mathcal{T}_{k}\}\) where \(\mathcal{T}_{i}=(T_{i},\phi_{i})\) for each \(i\in[k]\). Output: A tree \(\mathcal{T}=(T,\phi)\) that displays \(\mathcal{P}\), if \(\mathcal{P}\) is compatible; incompatible otherwise. 1 Construct \(H_{\mathcal{P}}(U_{\text{root}})\)
2\(Q\).enqueue\((\langle U_{\text{root}},\text{null}\rangle)\)
3 while\(Q\) is not emptydo
4\(\langle U,\text{pred}\rangle=Q\).dequeue\(()\)
5 Let \(S=\{v\in U:v\text{ is semi-universal in }U\}\)
6 if\(S=\emptyset\)then
7 returnincompatible
8 Create a node \(r_{U}\) where \(r_{U}\).parent\(=\)pred
9 if\(|S|=1\) and the single element \(v\in S\) is a leaf of \(H_{\mathcal{P}}\)then
10 Set \(\phi(r_{U})\) equal to the label of \(v\)
11 continue
12 Replace \(U\) by the successor of \(U\) with respect to \(S\)
13 Let \(W_{1},W_{2},\ldots,W_{p}\) be the connected components of \(H_{\mathcal{P}}(U)\)
14 foreach\(j\in[p]\)do
15\(Q\).enqueue\((\langle U|W_{j},r_{U}\rangle)\)
16 return\(\mathcal{T}=(T,\phi)\), where \(T\) is the tree with root \(r_{U_{\text{root}}}\)
```  
**Algorithm 1**BuildNT\((\mathcal{P})\). Figure 5: The root position \(U_{\text{root}}\) and its successor for the profile of Figure 1. Sets of nodes inside shaded boxes are positions. As a result of computing the successor, graph \(H_{\mathcal{P}}=H_{\mathcal{P}}(U_{\text{root}})\) breaks down into two components. In this example, all nodes in the positions shown are semi-universal. Note, however, that, in general, not all nodes in a position are semi-universal (see [9; 10]). There are two main contributors to the running time of BuildNT. The first is the time to compute the successor of \(U\) along with the connected components of \(H_{\mathcal{P}}(U)\) in Lines 12-13. Let \(U^{\prime}\) be the successor of \(U\) with respect to \(S(U)\). Then, \(H_{\mathcal{P}}(U^{\prime})\) can be obtained from \(H_{\mathcal{P}}(U)\) by doing the following for each \(v\in S(U)\): (1) for each \(i\in[k]\) such that \(U(i)=\{v\}\), delete all edges between \(v\) and \(\operatorname{Ch}_{i}(v)\); (2) delete \(v\). Using HDT (Section 2.2.2), each deletion takes \(O(\log^{2}M_{\mathcal{P}})\) amortized time. Since the total number of edge and node deletions is \(\mathcal{O}(M_{\mathcal{P}})\), the total work done in these lines is \(\mathcal{O}(M_{\mathcal{P}}\log^{2}M_{\mathcal{P}})\). If instead of HDT, we use its single-level version, HDT(0) (Section 2.2.3), then, by Proposition 1, the running time is \(\mathcal{O}(M_{\mathcal{P}}+s\log M_{\mathcal{P}})\), where \(s\) is the number of edge scans performed by BuildNT over its entire execution. The other main contributor to the running time of BuildNT is maintaining the semi-universal nodes of the various components that result from edge deletions, so that the labels can be quickly retrieved in Line 5.