## 2 Complexity Classification for General Digraphs  
In this section, we study the complexity of SP, LSP and SSP considering the most general case for the directed graph while putting very strong restrictions on the undirected graph \(G\). Our main result here is the following hardness result. **Theorem 1**. : Supported Path _is NP-hard even if \(G\) is a tree with two vertices that have degree at least three and one degree-two vertex._  
Proof. : We describe a reduction from the following NP-hard problem (see also Figure 1 for an illustration). Directed Disjoint Paths  
Instance: A directed graph \(H=(W,F)\), and \(k\) vertex pairs \((s_{i},t_{i})\), \(1\leq i\leq k\). Question: Is there a set of vertex-disjoint paths \(P_{i}\), each going from \(s_{i}\) to \(t_{i}\)? Directed Disjoint Paths are NP-hard even if \(k=2\)[22]. Let \((H,2)\) be an instance of Directed Disjoint Paths. Assume, without loss of generality, that \(s_{1}\) and \(s_{2}\) have only outgoing incident arcs and \(t_{1}\) and \(t_{2}\) have only incoming incident arcs. Furthermore, assume that \(t_{1}\) is not a neighbor of \(s_{1}\) (and note that it cannot be a neighbor of \(t_{2}\) by the assumption above). Furthermore, assume that \(N_{H}[s_{1}]\) and \(N_{H}[t_{2}]\) are disjoint. This can be easily achieved for example by subdividing the arcs incident with \(s_{1}\). Construct an instance of Supported Path as follows. First, initialize the directed graph as \(D:=H\) and add the arc \((t_{1},s_{2})\) to \(D\). Note that \(s_{2}\) is the only outneighbor of \(t_{1}\) and \(t_{1}\) is the only inneighbor of \(s_{2}\). Then, let \(G\) be the tree on \(W\) with the following properties:  
* \(t_{1}\) is a neighbor of \(t_{2}\) and \(s_{1}\),
* all neighbors of \(s_{1}\) in \(D\) are leaf neighbors of \(t_{2}\) and
* \(s_{2}\) and all other vertices of \(D\) are leaf neighbors of \(s_{1}\). Note that, by definition, in \(G\), all vertices are leaves, except \(t_{1}\), which has degree two, and \(s_{1}\) and \(t_{2}\), which have an arbitrarily large degree. We now show the equivalence of the instances, that is \(H\) has two vertex-disjoint paths from \(s_{1}\) to \(t_{1}\) and from \(s_{2}\) to \(t_{2}\) if and only if there exists a \((D,G)\)-supported path. \(\Rightarrow\): Let \(P_{1}\) and \(P_{2}\) be two vertex-disjoint paths in \(H\) from \(s_{1}\) to \(t_{1}\) and from \(s_{2}\) to \(t_{2}\), respectively. Then, the concatenation of \(P_{1}\) and \(P_{2}\) is a simple directed path in \(D\), since \(D\) additionally contains the arc \((t_{1},s_{2})\). Further, \(G[V(P_{1})\cup V(P_{2})]\) is connected, since all vertices that are in \(W\setminus(V(P_{1})\cup V(P_{2}))\) have degree one in \(G\), and thus, their deletion from \(G\) cannot make \(G\) disconnected. \(\Leftarrow\): Let \(P\) be a \((D,G)\)-supported path. Every edge in \(G\) has one of its endpoints in \(\{s_{1},t_{2}\}\). Hence, \(P\) contains either \(s_{1}\) or \(t_{2}\). Since \(P\) contains at least two nodes, then it contains, in \(D\), a neighbor of \(s_{1}\) or a neighbor of \(s_{2}\). All neighbors of \(s_{1}\) in \(D\) are leaf neighbors of \(t_{2}\) in \(G\), and all neighbors of \(t_{2}\) in \(D\) are leaf neighbors of \(s_{1}\) in \(G\) (recall that we assume \(N_{H}(t_{2})\) to be disjoint from \(N_{H}(s_{1})\)). Consequently, \(P\) contains \(s_{1}\) and \(t_{2}\) and, thus, also \(t_{1}\). Since \(s_{1}\) has no incoming arcs, \(P\) starts in \(s_{1}\), and since \(t_{2}\) has no outgoing arcs, \(P\) ends in \(t_{2}\). Consequently, \(P\) contains an outneighbor of \(t_{1}\), which by construction is \(s_{2}\). Hence, \(P\) is a simple path in \(D\) from \(s_{1}\) to \(t_{1}\) to \(s_{2}\) to \(t_{2}\). Hence, there are two vertex-disjoint paths \(P_{1}\) and \(P_{2}\) from \(s_{1}\) to \(t_{1}\) and from \(s_{2}\) to \(t_{2}\) in \(H\). \(\qed\)  
Hence, to obtain tractable cases for general \(D\), one would need to constrain \(G\) even further. If \(G\) is a bi-star, Shortest Supported Path and, thus, also Supported Path, are easily solvable in polynomial time.