## 4 Algorithms for Tree Compatibility and Incomplete Directed Perfect Phylogeny  
### Tree Compatibility  
BuildNT (Algorithm 1) builds a compatible supertree for a profile \(\mathcal{P}\) by traversing the display graph \(H_{\mathcal{P}}\) top-down, starting from the roots of the input trees, successively decomposing \(H_{\mathcal{P}}\) into subgraphs that correspond to subtrees of the compatible supertree [10]. If it is impossible to decompose \(H_{\mathcal{P}}\), the algorithm reports that \(\mathcal{P}\) is incompatible. To explain BuildNT in more detail, we need some definitions and notation. Figure 5 illustrates several of these notions. A _position_ in \(H_{\mathcal{P}}\) is a vector \(U=(U(1),\ldots,U(k))\), where \(U(i)\subseteq V(\mathcal{T}_{i})\), for each \(i\in[k]\). For each \(i\in[k]\), let \(\mathrm{Desc}_{i}(U)=\{v\in V(H_{\mathcal{P}})\,:\,v\text{ is a descendant of }v^{\prime}\text{ in }\mathcal{T}_{i}\text{ for some }v^{\prime}\,\in\,U(i)\}\), and let \(\mathrm{Desc}_{\mathcal{P}}(U)=\bigcup_{i\in[k]}\mathrm{Desc}_{i}(U)\). Note that, since labels may be shared among trees and \(H_{\mathcal{P}}\) is obtained by identifying leaves with the same label, we may have \(\mathrm{Desc}(U(i))\cap\mathrm{Desc}(U(j))\
eq\emptyset\), for \(i,j\in[k]\) with \(i\
eq j\). A position \(U\) is _valid_ if the following holds for each \(i\in[k]\). 1. If \(|U(i)|\geq 2\), then the elements of \(U(i)\) are siblings in \(\mathcal{T}_{i}\) and
2. \(\mathrm{Desc}_{i}(U)=\mathrm{Desc}_{\mathcal{P}}(U)\cap V(\mathcal{T}_{i})\). For any valid position \(U\), let \(H_{\mathcal{P}}(U)\) denote the subgraph of \(H_{\mathcal{P}}\) induced by \(\mathrm{Desc}_{\mathcal{P}}(U)\). Then, \(H_{\mathcal{P}}(U)\) is the subgraph of \(H_{\mathcal{P}}\) obtained by deleting all nodes in \(V(H_{\mathcal{P}})\setminus\mathrm{Desc}_{\mathcal{P}}(U)\), along with all incident edges [10]. Let \(U\) be a valid position, and let \(v\) be a vertex in \(U\). Then, \(v\) is _semi-universal in \(U\)_ if \(U(i)=\{v\}\), for every \(i\in[k]\) such that \(v\in V(\mathcal{T}_{i})\). Let \(S(U)\) denote the set of semi-universal labels in \(U\). The _successor of \(U\)_ is the position \(U^{\prime}\) such that, for each \(i\in[k]\), if \(U(i)=\{v\}\), for some \(v\in S(U)\), then \(U^{\prime}(i)=\mathrm{Ch}_{i}(v)\), where \(\mathrm{Ch}_{i}(v)\) denotes the set of children of \(v\) in \(V(\mathcal{T}_{i})\); otherwise, \(U^{\prime}(i)=U(i)\). The _root position_ is the position \(U_{\mathrm{root}}\) where, for each \(i\in[k]\), \(U_{\mathrm{root}}(i)\) is a singleton containing \(r(T_{i})\). It is obvious that \(U_{\mathrm{root}}\) is valid, that \(\mathrm{Desc}_{\mathcal{P}}(U_{\mathrm{root}})=V(H_{\mathcal{P}})\), that \(H_{\mathcal{P}}(U_{\mathrm{root}})=H_{\mathcal{P}}\), and that every vertex in \(U_{\mathrm{root}}\) is semi-universal. The key idea behind BuildNT is that if \(H_{\mathcal{P}}(U)\) is connected, then all semi-universal nodes in \(U\) can map to the same node \(r_{U}\) in a compatible supertree \(\mathcal{T}\) for \(\mathcal{P}\). The set of labels in the cluster at \(r_{U}\) is precisely the set of labels that appear in \(H_{\mathcal{P}}(U)\). Further, each connected component of \(H_{\mathcal{P}}(U^{\prime})\) corresponds to a distinct subtree of \(r_{U}\) in \(\mathcal{T}\). Figure 4: (**Left**) A character matrix \(A\). (**Right**) The display graph for \(\mathcal{P}_{A}\). The solid nodes and edges are the only part of the display graph that algorithm PPSS (Section 4.2) uses. BuildNT uses a first-in first-out queue \(Q\) to store pairs \(\langle U,\text{pred}\rangle\), where \(U\) is a valid position in \(\mathcal{P}\) and pred is a reference to the parent of the node corresponding to \(U\) in the supertree built so far. BuildNT initializes \(Q\) to contain the starting position, \(U_{\text{root}}\), with a null parent. Each iteration of the **while** loop of Lines 3-15 starts by de-queuing a pair \(\langle U,\text{pred}\rangle\). Line 5 computes the set \(S\) of semi-universal labels in \(U\).