## 4 Parameterized Hardness
Finally, \(D[V_{P}]\) is an induced path of length \(1+k^{2}\), which can be seen as follows. All vertices are on different levels of \(D\). For each \(i\leq k\), the vertex of \(V_{P}\) on level \(i\) has an arc to the vertex of \(V_{P}\) on level \(i+1\). Similarly, for each \(i\), \(1\leq i<k\cdot(k-1)/2\), the vertex of \(V_{P}\) on level \(k+2i\) has an arc to the vertex of \(V_{P}\) on level \(k+2i+1\). We now show that the remaining vertices of \(V_{P}\) also have arcs to the vertices of \(V_{P}\) on the next level. Observe that these vertices and the vertices on the next level correspond to edges of \(H\) whose endpoints have the same unordered color pair. Hence, consider two vertices in \(V_{P}\) corresponding to two edges of \(H\) with the same unordered color pair \(\{c(i),c(j)\}\). Since \(S\) is a clique, these two vertices in \(V_{P}\) are siblings, that is they correspond to the same undirected edge. Hence, there is in \(D\) an arc between the two vertices. Hence, \(D[V_{P}]\) is a connected graph containing one vertex from each level, and thus, it is a path of length \(k^{2}\). \(\Leftarrow\): Let \(P\) be a \((D,G)\)-supported path of length \(k^{2}\). Clearly, \(P\) contains exactly one vertex from each of the \(1+k^{2}\) levels of \(D\). Let \(S:=V(P)\cap W\). First, since \(P\) contains exactly one vertex from each level, \(S\) contains one vertex from each color class of \(H\). It remains to show that every pair of vertices \(u,v\in S\) is adjacent in \(H\). Again, since \(P\) contains exactly one vertex from each level, it contains two vertices corresponding to the unordered color pair \(\{c(u),c(v)\}\). Since there is an arc between these vertices, they are siblings, so we can call them \(v_{i,j}\) and \(v_{j,i}\), and we have \(\{i,j\}\in F\). The only neighbors of these vertices in \(G\) are \(i\) and \(j\), respectively. Since \(G[V(P)]\) is connected, we thus have \(\{i,j\}\in V(P)\). Furthermore, \(c(i)\
eq c(j)\), and thus, we can assume that \(c(i)=c(u)\) and \(c(j)=c(v)\). Since \(u\) is the only vertex in \(P\) with color \(c(u)\), we have \(i=u\). Similarly, \(j=v\). Hence, \(u\) and \(v\) are adjacent in \(H\). \(\Box\)  
Note that we can adapt the construction slightly in order to show W[1]-hardness for the problem of finding a \((D,G)\)-supported path of length at most \(k\). To achieve this, add two additional vertices \(t\) and \(w\) to the construction. Then, make \(t\) in \(D\) an outneighbor of all vertices in level \(k\) and an inneighbor of all vertices in level \(k+1\). Moreover, remove all arcs between level \(k\) and \(k+1\). Make vertex \(w\) an outneighbor of all vertices in the last level of \(D\). Now, modify \(G\) as follows: instead of making \(s\) adjacent to all vertices of the Levels \(1\) through \(k\), make \(w\) adjacent to these vertices. Then, make \(t\) adjacent to \(s\) and \(s\) adjacent to \(w\). With this construction, one can ensure that every \((D,G)\)-supported path takes one vertex from each layer plus \(t\) and \(w\). This can be seen as follows (recall that any \((D,G)\)-supported path must contain at least two vertices). If the path \(P\) contains vertex \(t\), then it must contain \(s\) and, therefore, also \(w\), since only \(w\) is in \(G\) adjacent to any further vertices. Similarly, if the path contains \(s\), then it must contain \(w\). If the path contains more than one vertex from Layer \(1\) through \(k\), then it must contain \(w\) and, thus, also \(t\) and \(s\). If the path contains any vertex from any other layer, then it must contain at least one vertex from Layers \(1\) through \(k\), which implies that it contains \(t\). Thus, in all cases, the path contains \(s\) and \(w\), which means that any \((D,G)\)-supported path, if it exists, has length \(k^{2}+2\). All other arguments remain the same. **Corollary 1**. : _The problem of deciding whether there is a \((D,G)\)-supported path of length at most \(k\) is W[1]-hard, even if \(D\) is acyclic and \(G\) is a tree of diameter four._