## 5 Enumeration-Based Algorithms  
We now describe two algorithms for deciding whether there is a \((D,G)\)-supported path of length exactly \(k\) that begins in a vertex \(u\) and ends in a vertex \(v\). Both algorithms work for general graphs \(G\) and \(D\). The first algorithm enumerates the paths of length \(k\) starting in \(u\).  
**Theorem 6**.: _Let \(\tilde{\Delta}\) denote the minimum of the maximum outdegree and the maximum indegree of \(G\). Given two vertices \(u,v\in V\), one can determine in \(O(\tilde{\Delta}^{k}\cdot|E|)\) time, by an algorithm that we call SPSearch(\(u,v,k\)), whether there is a \((D,G)\)-supported path of length \(k\) from \(u\) to \(v\)._  
Proof.: We describe the algorithm for the case that \(\tilde{\Delta}\) is the maximum outdegree of \(D\). The running time bound for the case that \(\tilde{\Delta}\) is the maximum indegree of \(D\) can be obtained by using the same algorithm on the instance that is obtained by reversing all arcs of \(D\) and searching for a \((D,G)\)-supported path from \(v\) to \(u\).  
The algorithm _SPSearch_(\(u,v,k\)) is a search tree algorithm. At the root, set \(P=(u)\), that is \(P\) is the trivial path of length zero that contains only \(u\). At each search tree node, we check whether there is a \((D,G)\)-supported path that has \(P\) as the prefix. If \(P\) has length \(k\), \(P\) is a path from \(u\) to \(v\) and \(G[V(P)]\) is connected, then return \(P\). Otherwise, abort the branch. If the length of \(P\) is at most \(k-1\), then find a solution recursively by extending \(P\). That is, for each arc \((w,x)\) in \(D\), where \(x\
otin V(P)\), search recursively for a solution whose prefix is \((u,\ldots,w,x)\) (the condition \(x\
otin V(P)\) is due to the fact that the solution has to be a simple path).  
This approach clearly finds a \((D,G)\)-supported path from \(u\) to \(v\) if it exists. The search tree has depth \(k\), and in each search tree node, the number of new branches is at most \(\tilde{\Delta}\). Moreover, in each search tree node, we can check in \(O(|E|)\) time whether \(G[V(P)]\) is connected.  
The second algorithm relies on an enumeration algorithm for connected subgraphs of order \(k\) in undirected graphs [25]. In the running time bound, \(e\) denotes Euler's number.  
**Theorem 7**.: _Let \(\Delta\) be the maximum degree of \(G\) and \(\tilde{\Delta}\) be the minimum of the maximum outdegree and maximum indegree of \(D\). Given two vertices \(u,v\in V\), one can determine in \(O((2\cdot e\cdot\Delta)^{k}\cdot(\Delta+k)\cdot\tilde{\Delta}k^{3})\) time whether there is a \((D,G)\)-supported path of length \(k\) from \(u\) to \(v\)._  
Proof.: Assume first that a vertex set \(S\) of size \(k\) is given and that we need to determine whether \(D[S]\) has a \((D,G)\)-supported path from \(u\) to \(v\) of length \(|S|-1\). That is, we check whether \(D[S]\) has a Hamiltonian path that starts in \(u\) and ends in \(v\). Since \(|S|=k\), this can be done in \(O(2^{k}\cdot k^{2}+\tilde{\Delta}k)\) time by first building \(D[S]\) in \(O(\tilde{\Delta}k)\) time and then applying the standard dynamic programming algorithm for the Traveling Salesman[26, 27].  
Now, to obtain \(S\) or to determine that no suitable \(S\) exists, we can use the fact that all connected subgraphs of \(G\) that contain \(u\) and have \(k\) vertices can be enumerated in \(O((e\cdot(\Delta-1))^{k}\cdot(\Delta+k)k)\) time [25]. The overall running time bound follows by multiplying the number of enumerated subgraphs by the time needed to verify the existence of a Hamiltonian path in each \(D[S]\).