## 7 Analysis
### The Impact of Deleting Non-Tree Edges  
We first examine the prevalence of non-tree edge deletions and their total contribution to the execution time. Recall that each such deletion takes \(\mathcal{O}(1)\) time (Proposition 2(1a)).  
Table 3 shows HDT(0)'s performance on complete sets of triples. The first row of the table shows the ratio of the number of actually deleted non-tree edges to the total number of edges in \(H_{\mathcal{P}}\). The second row shows the percentage of time that HDT(0) spends on deleting non-tree edges. Both numbers are small, indicating that the work is dominated by processing tree edges.  
Tables 4 and 5 show the running time of FCT(0) on profiles of binary phylogenetic trees. Similar to the situation for triples, the number of non-tree edge deletions and the amount of time performing them is relatively small.  
\begin{table}
\begin{tabular}{c c c c c c c c c c} \hline \hline \(M_{\mathcal{P}}\) & **10,000** & **20,000** & **30,000** & **40,000** & **50,000** & **60,000** & **70,000** & **80,000** & **90,000** & **100,000** \\ \hline \(Num(NTE)\) & 17.13\% & 17.32\% & 17.25\% & 17.27\% & 17.25\% & 17.27\% & 17.35\% & 17.35\% & 17.32\% & 17.42\% \\ \(Time(NTE)\) & & & & & & & & & \\ \(Time(HDT)\) & 8.03\% & 7.97\% & 7.64\% & 7.82\% & 7.81\% & 7.58\% & 7.69\% & 7.58\% & 7.62\% & 7.63\% \\ \hline \hline \end{tabular}
\end{table}
Table 4: FCT(0) on profiles of binary phylogenetic trees for \(k=100\) and varying \(n\): Ratio of number of deleted non-tree edges to total HDT execution time.  
\begin{table}
\begin{tabular}{c c c c c c c c c c} \hline \hline \(M_{\mathcal{P}}\) & **65** & **730** & **2745** & **6860** & **13,825** & **24,390** & **39,305** & **59,320** & **85,185** & **117,650** \\ \hline \(Num(NTE)\) & 9.25\% & 19.51\% & 21.88\% & 21.08\% & 22.49\% & 23.00\% & 23.20\% & 22.49\% & 23.05\% & 23.13\% \\ \(Time(NTE)\) & 7.48\% & 9.49\% & 10.04\% & 9.86\% & 10.09\% & 10.28\% & 10.22\% & 9.99\% & 9.99\% & 9.83\% \\ \hline \hline \end{tabular}
\end{table}
Table 3: FCT(0) on complete sets of triples: Ratio of number of deleted non-tree edges to total number of edges and ratio of time spent on deleting non-tree edges to total HDT execution time.  
\begin{table}
\begin{tabular}{c c c c c c c c c c} \hline \hline \(M_{\mathcal{P}}\) & **10,000** & **20,000** & **30,000** & **40,000** & **50,000** & **60,000** & **70,000** & **80,000** & **90,000** & **100,000** \\ \hline \(Num(NTE)\) & 17.87\% & 18.76\% & 18.76\% & 18.79\% & 18.76\% & 19.17\% & 19.33\% & 19.13\% & 19.11\% & 19.35\% \\ \(Time(NTE)\) & & & & & & & & & \\ \(Time(HDT)\) & & & & & & & & & & \\ \hline \hline \end{tabular}
\end{table}
Table 5: FCT(0) on profiles of binary phylogenetic trees for \(n=100\) and varying \(k\): Ratio of number of deleted non-tree edges to total number of edges and ratio of time spent on deleting non-tree edges to total HDT execution time.  
Tables 6 and 7 show the running time of FCT(0) on phylogenetic trees where internal node have degree seven. As expected, by increasing the degree of internal nodes, we increased the number of non-tree edges. On the other hand, the contribution of these edges to the total running time did not increase markedly.  
Tables 3-7 indicate that to get a better understanding of the behavior of FCT(0) on profiles of low-degree trees, it is necessary to focus on tree edge deletions and, more specifically, on the time spent scanning for replacement edges. We study this issue in the next section. Before doing so, we consider the case of high-degree vertices, which is encountered in IDPP.  
Tables 8-10 show the performance of FPP(0) on low-, medium-, and high-density inputs. The results show that deletions were mostly done on the non-tree edges, which makes sense due to their relative abundance. Further, the program spent a large fraction of its time (in some cases, upwards