## 7 Experiments  
To assess the range of instances that can be solved by enumeration-based algorithms, we performed experiments on biological and synthetic data. We implemented and evaluated both algorithms. Experimental Setup and Implementation Details.Our algorithms were implemented in Python, Version 2.7.3; source code and data are publicly available [28]. We used the NetworkX package for the graph data structures and basic graph algorithms, such as computing the shortest path. The test machine is a 4-core 3.6-GHz Intel Xeon E5-1620 (Sandy Bridge-E) with 10 MB L3 cache and 64 GB main memory, running under Debian GNU/Linux 7.0. We report wall-clock times. In all experiments, a timeout threshold of 30 seconds was used. The reported running times do not include the time for the first pass of Rules 1 to 3 (as it was performed only once in advance for the biological instance), but they include the time needed for the exhaustive application of all other data reduction rules. The first pass of Rules 1 to 3 takes less than \(0.01\) s in all instances and is thus negligible. The algorithm that enumerates paths, which we will call the path enumeration algorithm, is implemented as follows. Given a pair of vertices \(u\) and \(v\), it tries to determine whether there is a \((D,G)\)-supported path from \(u\) to \(v\) as follows. First, perform the data reduction rules exhaustively. Then, determine for increasing values of \(k\) whether there is a \((D,G)\)-supported path of length at most \(k\) from \(u\) to \(v\). This is done by invoking the enumeration algorithm _SPSearch\((u,v,k)\)_ in Theorem 6. The initial \(k\) is the maximum of the length of a shortest path from \(u\) to \(v\) in \(D\) and in \(G\). Moreover, when branching into the cases to extend a path \((u,\ldots,w)\) by a vertex \(x\), we perform a check based on the following observation. **Observation 1**. : _If \((u,\ldots,w)\) is a path of length \(\ell\) and the shortest path from \(x\) to \(v\) has length at least \(k-\ell\), then there is no \((D,G)\)-supported path of length at most \(k\) with prefix \((u,\ldots,w,x)\)._That is, we check for each arc \((w,x)\) whether taking the shortest path from \(x\) to \(v\) gives a path of length at most \(k\). If this is not the case, then \(x\) is discarded. In preliminary experiments, we also tested whether reversing \(D\) and starting the search from \(v\) instead of \(u\) has an impact on the running time. Unfortunately, even if one runs both (direct and reverse) algorithms in parallel (that is, one only retains the minimum of the running times of the two algorithms), this approach does not yield a substantial speedup. For the algorithm that enumerates connected subgraphs of \(G\), that we call the tree enumeration algorithm (since it essentially enumerates spanning trees of subgraphs of \(G\)), we used a simple procedure for the subgraph enumeration that maintains a set \(S\), such that \(u\in S\) and \(G[S]\) is connected. If \(|S|=k+1\) and \(v\in S\), then the algorithm checks whether \(D[S]\) has a Hamiltonian path from \(u\) to \(v\). Otherwise, it recursively extends \(S\) by considering each neighbor of a vertex in \(S\). In this procedure, we use the two following observations for early termination of the subgraph enumeration. The first observation identifies sets that are too far from \(v\). **Observation 2**. : _If \(v\
otin S\) and all vertices in \(S\) have distance at least \(k-|S|+2\) to \(v\), then there is no order-\((k+1)\) set \(S^{\prime}\) such that \(S\subset S^{\prime}\), \(v\in S^{\prime}\) and \(G[S^{\prime}]\) is connected._  
The second observation identifies sets \(S\) such that the number of arcs in \(D[S]\) is too low to obtain a directed path from \(u\) to \(v\). **Observation 3**.