## Chapter 8 Appendix Path (SP)  
Instance: A directed graph \(D=(V,A)\) and an undirected graph \(G=(V,E)\). Question: Is there a \((D,G)\)-supported path? In applications, one might additionally try to optimize certain criteria of such a path. We study here the fundamental problems of maximizing or minimizing path length:  
Longest Supported Path (LSP)  
Instance: A directed graph \(D=(V,A)\) and an undirected graph \(G=(V,E)\). Task: Find the longest \((D,G)\)-supported path. Shortest Supported Path (SSP)  
Instance: A directed graph \(D=(V,A)\) and an undirected graph \(G=(V,E)\). Task: Find the shortest \((D,G)\)-supported path. In this work, we study the complexity landscape of these computational problems by identifying polynomial-time solvable, as well as NP-hard cases of the problem. Clearly, more general variants of the problem, for example when \(D\) and \(G\) have different, but related vertex sets, may be also useful in practice, but their study is beyond the scope of this work. Before presenting our main results, we make some basic observations on the complexity of the problems. First, with respect to polynomial-time solvability, SP is clearly not harder than SSP and LSP. Moreover, consider the special case in which \(G\) is a clique. This simply means that the graph \(G\) does not put any additional constraints on the desired paths. In this case, SP and SSP reduce to the polynomial-time problem of deciding whether \(D\) has at least one arc, but LSP is the NP-hard Longest Path path problem. Therefore, intuitively, LSP is the hardest of the three problems. Note that for LSP, the special case in which the directed graph \(D\) is a DAG and in which \(G\) is a clique is polynomial-time solvable, since it reduces to finding the longest path in a DAG. Preliminaries.Throughout the paper, \(D\) will denote a directed graph and \(G\) an undirected graph, built on the same vertex set \(V\). We use \(n:=|V|\) to denote the number of vertices in \(D\) (or equivalently, in \(G\)). Given a graph \(H\) and a set \(S\subseteq V(H)\), let \(H[S]\) denote the subgraph of \(H\) induced by \(S\), that is the graph with vertex set \(S\) and all edges (arcs) of \(H\) that have both endpoints in \(S\). We use \(N_{H}(v)\) to denote the neighborhood of a vertex \(v\) in a graph \(H\) and \(N_{H}[v]:=N_{H}(v)\cup\{v\}\) to denote the closed neighborhood of \(v\) in \(H\). A path \(P\) is called simple if it contains every vertex of \(V(P)\) exactly once. A star is a tree with one non-leaf, a bi-star is a tree with two non-leafs. The diameter of a graph is the maximum length of a shortest path between any two of its vertices. An outerplanar graph is a graph admitting a planar embedding with all vertices on a circle, all edges inside the circle and such that edges do not cross each other. A problem with input size \(n\) is called fixed-parameter tractable with respect to a parameter \(k\) if it can be solved in \(f(k)\cdot n^{O(1)}\) time, where \(f\) is a computable function only depending on \(k\). A fundamental class of presumed parameterized intractability is called W[1]. Hardness for W[1] can be shown by a parameterized reduction from a problem that is known to be W[1]-hard. A parameterized reduction transforms an instance \((X,k)\) of a parameterized problem \(L\) in \(f(k)\cdot|X|^{O(1)}\) time into an equivalent instance \((X^{\prime},k^{\prime})\) of a parameterized problem \(L^{\prime}\). We refer to [18; 19; 20] for further details concerning parameterized complexity. Our Results.Our findings for the three problems can be summarized as follows (see Table 1 for an overview, where \(h\) is the number of vertices of degree two or more). Here, for any directed graph \(H\), the underlying undirected graph of \(H\), denoted \(H^{*}\), is the graph that is obtained from \(H\) simply by removing arc directions. If the underlying undirected graph \(D^{*}\) of \(D\) is a tree, then all three problems can be solved in polynomial time. If \(D^{*}\) is outerplanar, then LSP is already NP-hard.