## 7 Analysis  
In our experiments, the most striking and consistent observation was the effectiveness of HDT(0) for both compatibility testing and IDPP, across the entire range of inputs considered. A partial explanation is that HDT(0) incurs far less overhead than HDT. This, however, does not fully explain why the running time of FCT(0) was close to \(O(M_{\mathcal{P}}\log M_{\mathcal{P}})\) in practice. Theorem 1 indicates that this performance may be tied to the small number of edge scans performed throughout the execution of the algorithms. Here, we explore this issue in more detail. First, we break down in more detail the factors that affect the performance of HDT(0) in BuildNT and PPSS. For each vertex \(v\in V(H_{\mathcal{P}})\), let \(d_{v}\) denote the number of children of \(v\). At any stage of its execution, BuildNT maintains a graph \(H\) obtained from \(H_{\mathcal{P}}\) through edge and node deletions. Because these deletions are performed top-down, the number of edges incident on any node \(v\) in \(H\) is at most \(d_{v}\). Lemma 2: _Let \(e=(u,v)\) be a tree edge in the current spanning forest \(F\) maintained by HDT(0) during the execution of BuildNT (or PPSS), and let \(T_{u}\) and \(T_{v}\) be the two trees that result from deleting \(e\) from the tree in \(F\) that contains \(e\). Assume, without loss of generality, that \(|V(T_{u})|\leq|V(T_{v})|\). Then, searching for a replacement edge for \(e\) requires scanning at most \(2+\sum_{w\in V(T_{u})}(d_{w}-1)\) non-tree edges._  
Proof: We claim that the number of non-tree edges scanned is at most one more than the number of edges with both endpoints in \(T_{u}\). To see why, note that the scan for a replacement edge stops as soon as either (i) we encounter an edge that has one endpoint, \(x\), in \(T_{u}\) and the other, \(y\), outside \(T_{u}\) (and, thus, \((x,y)\) is a replacement edge) or (ii) we find that all non-tree edges incident on \(T_{u}\) have both of their endpoints in \(T_{u}\) (and, thus, no replacement edge exists). To complete the proof, we argue that the number of non-tree edges with both endpoints in \(T_{u}\) is at most \(1+\sum_{w\in V(T_{u})}d_{w}\). \begin{table}
\begin{tabular}{c c c c c c c c c c c} \hline \hline  & **5\%** & **10\%** & **15\%** & **20\%** & **25\%** & **30\%** & **35\%** & **40\%** & **45\%** & **50\%** \\ \hline FCT(0) & 10.07 & 10.00 & 9.87 & 9.61 & 9.52 & 9.41 & 9.36 & 9.07 & 9.05 & 8.80 \\ FPP(0) & 6.43 & 6.48 & 6.38 & 6.32 & 6.43 & 5.68 & 6.30 & 6.55 & 6.44 & 6.12 \\ Connectivity (FCT) & 3.37 & 3.37 & 3.32 & 3.24 & 3.28 & 3.22 & 3.30 & 3.16 & 3.15 & 3.07 \\ Connectivity (FPP) & 1.38 & 1.36 & 1.33 & 1.28 & 1.36 & 1.26 & 1.35 & 1.42 & 1.38 & 1.30 \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Comparison between execution time (in seconds) of the tree compatibility algorithm on transformed IDPP and original IDPP on high-density matrices of order 100 \(\times\) 2000. Let \(m_{u}\) be the total number of tree and non-tree edges incident on \(V(T_{u})\). Then, \(m_{u}\leq\sum_{v\in V(T_{u})}d_{uv}\). The number of tree edges with both endpoints in \(V(T_{u})\) is \(m^{\prime}_{u}=|V(T_{u})|-1\). The number of non-tree edges is thus \(m_{u}-m^{\prime}_{u}\leq\sum_{v\in V(T_{u})}d_{uv}-(|V(T_{u})|-1)\leq 1+\sum_{v \in V(T_{u})}(d_{uv}-1)\), as claimed. **Proposition 2**. : _Let \(F\) be the current spanning forest maintained by \(\mathrm{HDT}(0)\) during the execution of BuildNT (or_ PPSS_); let \(v\) be the semi-universal node being processed during the computation of the next successor position; and let \(e\) be the next edge incident on \(v\) to be deleted. Then, the following hold._  
1. _Deleting_ \(e\) _takes:_ 1. \(\mathcal{O}(1)\) _time if_ \(e\) _is a non-tree edge,_ 2. \(\mathcal{O}(\log M_{\mathcal{P}})\) _time if_ \(e\) _is the only tree edge incident on_ \(v\)_, and_ 3. \(\mathcal{O}(\min\{\sum_{v\in V(T)}d_{uv},|V(T)|^{2}\}\cdot\log M_{\mathcal{P}})\) _time otherwise, where_ \(T\) _is the smaller of the two trees created by deleting_ \(e\) _from_ \(F\)_.