## 7 Experiments
For the path enumeration algorithm, the case when \(G\) is sparse compared to \(D\) is difficult. Here, the tree enumeration algorithm performs better both in sparse and in dense instances. The reason is most likely that in this case, short paths in \(D\) are unlikely to induce connected graphs in \(G\). Conversely, the case in which \(G\) is dense compared to \(D\) appears to be easily solvable by the path enumeration algorithm on graphs with up to 100 vertices. Our experiments furthermore suggest that running times depend less on the vertex number than on the density of the respective graphs. Data reduction is much less effective on synthetic data: it very rarely reduces the number of edges or vertices at all. This suggests that the data reduction rules efficiently exploit the structure of real-world instances. Altogether, the experiments show that it may make sense to first compute the density of the two input graphs and then to choose the correct algorithm. \begin{table}
\begin{tabular}{c c c c c c c c c} \hline \hline  & \(\mathbf{n}\) & \(\mathbf{m_{D}}\) & \(\mathbf{\Delta^{+}}\) & \(\mathbf{\Delta^{-}}\) & \(\mathbf{c_{D}}\) & \(\mathbf{m_{G}}\) & \(\mathbf{\Delta}\) & \(\mathbf{c_{G}}\) \\ \hline input & 301 & 1221 & 35 & 49 & 6 & 1402 & 59 & 2 \\ after Rules 1–3, 5, 6 & 104.6 & 526.9 & 25.8 & 24.4 & 1 & 270.4 & 22.2 & 1 \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Instance properties and effect of data reduction. Here, \(n\) denotes the number of vertices, \(m_{D}\) and \(m_{G}\) denote the number of edges in \(D\) and \(G\), \(\Delta^{+}\) denotes the maximum outdegree in \(D\), \(\Delta^{-}\) denotes the maximum outdegree in \(D\), \(\Delta\) denotes the maximum degree in \(G\) and \(c_{D}\) and \(c_{G}\) denote the number of connected components in \(D\) and \(G\). The values in the second line are arithmetic means over those instances that where not solved by the data reduction; Rule 4 is excluded since it depends on \(k\). Figure 4: Running times for the biological data. (**Left**) The running times of the path enumeration algorithm with restricted and unrestricted path length; (**right**) the running times of the tree enumeration algorithm. Figure 5: Comparison of the path enumeration algorithm and the tree enumeration algorithm in sparse synthetic data. In the legend, the first number is \(p_{D}\) and the second number is \(p_{G}\). (**Left**) \(n=50\); (**right**) \(n=100\). Figure 6: Comparison of the path enumeration algorithm and the tree enumeration algorithm in dense synthetic data. In the legend, the first number is \(p_{D}\) and the second number is \(p_{G}\). (**Left**) \(n=50\); (**right**) \(n=100\). As a final remark on random graphs, the fact that dense graphs are easily solvable is not surprising: for a fixed vertex \(w\), the probability that there is a path \((u,w,v)\) in \(D\) is \(p_{D}\cdot p_{D}\). The probability that \(G[\{u,v,w\}]\) is connected is: \(p_{G}^{3}+3\cdot p_{G}^{2}\cdot(1-p_{G})\). Thus, for constant values of \(p_{D}\) and \(p_{G}\), the probability that a vertex pair \((u,v)\) has a \((D,G)\)-supported path in \(n\)-vertex graph is one in the limit. Biological Examples.A short \((D,G)\)-supported path that was found in the biological dataset is ENO2 \(\rightarrow\) ARO1 \(\rightarrow\) BNA4 \(\rightarrow\) ALD6. Interestingly, ENO2 and ALD6 encode enzymes of the glucose fermentation pathway, whereas the enzymes encoded by ARO1 and BNA4 are not annotated as parts of this pathway. Ideally, the existence of an alternative short \((D,G)\)-supported path between ENO2 and ALD6 could either point to alternative (sub)pathways for glucose fermentation or to missing data in the yeast protein interaction network. The longest \((D,G)\)-supported path that was found is the length 13 path HOM6 \(\rightarrow\) HOM2 \(\rightarrow\) BNA4 \(\rightarrow\) ARO1 \(\rightarrow\) ARO2 \(\rightarrow\) TRP3 \(\rightarrow\) GDH3 \(\rightarrow\) AAT2 \(\rightarrow\) GDH2 \(\rightarrow\) SER1 \(\rightarrow\) ALT1 \(\rightarrow\) ARO9 \(\rightarrow\) AGX1 \(\rightarrow\) GCV2.