## 7 Experiments
: _If \(D[S]\) has less than \(k-(2(k+1-|S|))\) arcs, then there is no order-\((k+1)\) set \(S^{\prime}\) such that \(S\subset S^{\prime}\), \(D[S^{\prime}]\) has a Hamiltonian path._  
The correctness stems from the fact that the desired path has \(k\) arcs and that every deletion of a vertex can remove at most two path arcs from the graph. Unfortunately, the second observation yields a reduction only if \(|S|>k/2\). Nevertheless, it proved to be crucial for this algorithm, as without the corresponding early termination rule, the number of enumerated subgraphs is too large. Biological Data.We downloaded the biochemical pathways information from the _Saccharomyces_ Genome Database (SGD) [29], which contains for each enzyme of _S. cerevisiae_ a mapping from its EC (enzyme catalog) number to its gene identifier. Then, also from SGD, we obtained the protein interactions for the proteins encoded by these genes. To obtain the reactions from the EC numbers, we used the Explore Enz database [30]: For each pair of EC numbers \(x\) and \(y\), we checked whether there is at least one product of \(x\) that is a substrate of \(y\). If this were the case, then the arc \((g_{x},g_{y})\) was added to \(D\), where \(g_{x}\) and \(g_{y}\) are the gene identifiers associated with the EC numbers \(x\) and \(y\), respectively. To restrict the product/substrate relationships in the directed graph to meaningful ones, we excluded five frequent metabolites (\"ATP\", \"ADP\", \"AMP\", \"H\({}_{2}\)O\" and \"H\({}^{+}\)\") that have high abundance in the cell. For the resulting pair of directed graph \(D\) and undirected graph \(G\), we randomly sampled 500 vertex pairs and tried to determine for each pair \((u,v)\) whether there is a \((D,G)\)-supported path from \(u\) to \(v\). Synthetic Data.We performed experiments on random graphs with \(n=50\) and \(n=100\) vertices. The undirected graphs are created using the \(G_{n,p}\)-model due to [PERSON], Renyi and Gilbert, where each edge is present with a fixed probability \(p\). Similarly, in the directed graph, each arc is present with a fixed probability \(p\), that is for each pair of vertices \(u\) and \(v\), the arc \((u,v)\) is present with probability \(p\) and the arc \((v,u)\) is also present with probability \(p\). We use \(p_{G}\) to denote the probability used for generating \(G\) and \(p_{D}\) to denote the one for generating \(D\). For each value of \(n\), we created two classes of instances: (i) sparse instances for which either \(p_{G}=0.05\) and \(p_{D}=0.1\) or \(p_{G}=0.1\) and \(p_{D}=0.05\); and (ii) dense instances for which either \(p_{G}=0.1\) and \(p_{D}=0.5\) or \(p_{G}=0.5\) and \(p_{D}=0.1\). For each triple of values of \(n\), \(p_{G}\) and \(p_{D}\), we created 500 instances and randomly picked a pair of vertices \(u\) and \(v\) such that we aim to find a \((D,G)\)-supported path from \(u\) to \(v\) (we chose a higher number of pairs for the real-world instance to compensate for the fact that we considered only one biological instance). Experimental Results.We first describe the experiments on the biological data. Some properties of the two networks and the effect of the data reduction rules are shown in Table 2. It can be seen that the data reduction substantially reduces the size of the remaining instances. In addition, for 358 of 500 random endpoint pairs, the data reduction solved the instance directly (by removing either \(v\) or \(u\)). Our running time results for both algorithms are shown in Figure 4. As expected, searching only for short paths is much easier than considering all solutions. In particular, we conclude that \((D,G)\)-supported paths of length at most eight can be found quickly with both algorithms. Path enumeration is consistently faster, but the difference is slightly less pronounced for \(k\leq 8\). Our results for the experiments with synthetic data are shown in Figures 5 and 6. Our main observations here are that sparser instances are harder than dense instances.