## 1 Introduction
### Background  
Tree compatibility testing arises in _supertree construction_[4; 5; 6; 7], where the goal is to assemble a comprehensive phylogenetic tree out of smaller trees for restricted sets of taxa. The tree compatibility problem, however, has wider uses. In fact, the first polynomial-time algorithm for testing tree compatibility, the Build algorithm of [PERSON] et al. [8], was designed to solve a problem in relational databases, not phylogenetics. The connection with phylogenetics was noted later [1]. A recent algorithm, called BuildNT[9; 10], solves the tree compatibility problem for an arbitrary profile \(\mathcal{P}\) in \(\mathcal{O}(M_{\mathcal{P}}\log^{2}M_{\mathcal{P}})\) time, where \(M_{\mathcal{P}}\) denotes the total size of the trees in \(\mathcal{P}\). BuildNT is closely related to Semple and Steel's version of Build[2] (the suffix \"NT\" refers to the fact that the algorithm can be extended to profiles of trees with \"nested taxa\"; i.e., where internal nodes are labeled with higher order species [10]). There is one important difference between the two algorithms. Build relies on the _triple graph_, whose nodes are the species and where there is an edge between two species \(a\) and \(b\) if they are involved in a _rooted triple_ in some input tree; that is, if there is a third species \(c\) such that, for some input tree, the lowest common ancestor of \(a\) and \(b\) is a descendant of the lowest common ancestor of \(a\), \(b\), and \(c\). In contrast, BuildNT relies on the _display graph_ of the profile, a graph that was first studied in the context of testing the compatibility of unrooted trees [11]. The display graph is closely related to the intersection graph of certain sets of _clusters_ that appear in the input trees (a cluster is a set of species that descend from the same node). As explained in [9], this cluster-based view provides a link to Build's triplet-based approach. It also leads to improved performance for high-degree trees. BuildNT, and essentially every other known algorithm for tree compatibility, involves maintaining the connected components of a graph under a series of edge and vertex deletions [9; 12; 13]. Thus, the efficiency of these algorithms depends heavily on the dynamic graph connectivity data structure used. Conversely, tree compatibility has been cited as a motivation for developing efficient dynamic graph connectivity data structures [12; 14; 15]. IDPP arises when building phylogenetic trees based on rare genomic changes, such as the insertion of short interspersed nuclear elements (SINEs) [13; 16]. IDPP is also useful for resolving genotypes into haplotypes [17]. The algorithm of [PERSON] et al. [13] solves IDPP for an \(n\times k\) matrix \(A\) in \(O(nk+m\log^{2}(n+k))\) time, where \(m\) denotes the number of ones in \(A\). This algorithm also relies on dynamic graph connectivity. Several dynamic graph connectivity data structures have been proposed [18; 19; 20; 15; 21]. Notable among them is the data structure of [PERSON] et al., known as _HDT_[15; 20]. HDT allows one to maintain a graph under a sequence of vertex and edge deletions and insertions in polylogarithmic amortizedtime per operation. The above-mentioned time bounds for tree compatibility and IDPP are based on using HDT. Like other dynamic connectivity data structures, HDT maintains a spanning forest of the given graph, where there is one spanning tree for each connected component. Edges in the forest are called _tree edges_. The deletion of a tree edge breaks a tree in two and triggers the search for an edge, called a _replacement edge_, to re-link the trees. To ensure polylogarithmic amortized time per update, HDT stores edges in a multi-level structure, where an edge can appear in multiple levels (see Section 2.2). To our knowledge, there is no previously-published computational study of any tree compatibility algorithm. There is, however, a previous experimental study of HDT [22]. That paper offers insights into the implementation details and the factors that affect HDT's performance in practice.