## Chapter 8 Appendix Path (SP)
If \(D^{*}\) has treewidth three, then even SP is NP-complete. These hardness results hold even if \(D\) is acyclic and \(G\) is a tree with diameter four. For general digraphs, all problems become hard even if \(G\) is a tree with a constant number, at least three, of non-leaf vertices. In contrast, if \(D\) is acyclic, then all three problems become fixed-parameter tractable with respect to the number of vertices with degree at least two in \(G\). These general complexity results are presented in Section 2 (which considers general digraphs) and Section 3 (which considers the special case where \(D\) is acyclic). In Section 4, we then study the parameterized complexity of the problems, showing that deciding whether \(G\) contains a \((D,G)\)-supported path of length exactly \(k\) is W[1]-hard, that is a fixed-parameter algorithm for this parameter is unlikely. Thus, a running time of \(n^{f(k)}\) seems to be more or less unavoidable for finding \((D,G)\)-supported paths of length \(k\). This holds even if \(G\) is a tree and \(D\) is acyclic. In Section 5, we propose two enumeration-based algorithms for solving the problem of finding \((D,G)\)-supported paths of length exactly \(k\). One algorithm is a fixed-parameter algorithm for the combined parameter \((\tilde{\Delta},k)\), where \(\tilde{\Delta}\) is the minimum of the maximum outdegree and maximum indegree in \(D\). The other algorithm is a fixed-parameter algorithm for the combined parameter \((\Delta,k)\), where \(\Delta\) is the maximum degree in \(G\). Furthermore, we describe in Section 6 several data reduction rules that are used in the implementation of our algorithms. \begin{table}
\begin{tabular}{c c c c} \hline \hline \multirow{2}{*}{\(G\)} & \multicolumn{3}{c}{**Acyclic \(D\)**} \\ \cline{2-4}  & \multicolumn{2}{c}{\(D^{*}\)} & **General \(D\)** \\ \cline{2-4}  & **Tree** & **Outerplanar** & **Treewidth 3** \\ \hline path or cycle & & P (Proposition 2) & NPC [21] \\ \hline \multirow{4}{*}{\(h\) vertices degree \(\geq 2\)} & & & LSP, \(h=1\): NPC (Theorem 2) \\  & & \(2^{h}\cdot n^{O(1)}\) (Proposition 2) & SSP, \(h=2\): P (Proposition 1) \\  & & & SSP, SP, \(h=3\) and \(G\) is a tree: \\  & & & NPC (Theorem 1) \\ \hline tree with diameter \(4\) & P \(\downarrow\) & LSP: NPC (Theorem 3) & NPC (Theorem 4) & NPC \(\uparrow\) \\ \hline general graph & P (Proposition 2) & LSP: NPC \(\uparrow\) & NPC \(\uparrow\) & NPC \(\uparrow\) \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Complexity of the variants of Supported Path. Herein, \(D^{*}\) is the underlying undirected graph of \(D\). If no problem names are specified, then the results hold for SP, Longest Supported Path (LSP)and Shortest Supported Path (SSP); arrows indicate that a result is implied by another result in the table. In Section 7, we evaluate our two enumeration-based algorithms on synthetic and biological data. Our main observations are that finding \((D,G)\)-supported paths with at most eight vertices is tractable in the considered biological network and that the case in which \(G\) is very sparse compared to \(D\) is hard to handle for our algorithm. This is in line with our theoretical findings that show that all three problem variants remain hard if \(G\) is a tree. In Section 8, we conclude with a summary of our results and directions for future research.