## 4 Parameterized Hardness  
The hardness results presented so far do not exclude efficient algorithms for the case in which one is satisfied with finding a \((D,G)\)-supported path of length exactly \(k\) for some given constant \(k\). Such an algorithm might be interesting for example in case the longest path in \(D\) has bounded length. In fact, an \(n^{k+O(1)}\)-time algorithm for this problem is easily achievable by guessing the vertices of the path in the correct order and then checking in polynomial time whether the subgraph of \(G\) is connected. As we show in the following, it is unlikely that this can be improved to a running time of \(f(k)\cdot n^{O(1)}\). **Theorem 5**. : _The problem of deciding whether there is a \((D,G)\)-supported path of length exactly \(k\) is W[1]-hard even if \(D\) is acyclic and \(G\) is a tree of diameter four._  
Proof. : We describe a parameterized reduction from the W[1]-hard Multicolored Clique problem [24]:  
Instance: An undirected graph \(H=(W,F)\) with a proper vertex coloring \(c:V\rightarrow\{1,\ldots,k\}\). Question: Is there a clique \(S\) of order \(k\) in \(H\) such that \(S\) contains one vertex from each color? Given an instance of Multicolored Clique, the instance of Supported Path is constructed as follows. The vertex set is \(W\cup\bigcup_{\{i,j\}\in F}\{v_{i,j},v_{j,i}\}\cup\{s\}\), that is we create one vertex for each vertex of \(H\), two vertices for each edge of \(H\) and one additional vertex \(\{s\}\). We call the two vertices that correspond to the same edge in \(H\) siblings. In the construction, assume that an arbitrary, but fixed ordering of unordered color pairs is given. The directed graph has the following \(1+k^{2}\) levels:  
* Level 0 contains \(s\),
* level \(i\), \(1\leq i\leq k\), contains all vertices of \(W\) that have color \(i\),
* level \(k+2i-1\), \(1\leq i\leq k\cdot(k-1)/2\), contains all vertices \(v_{j,\ell}\) where \(\{c(j),c(\ell)\}\) is the \(i\)-th color pair and \(c(j)<c(\ell)\) and
* level \(k+2i\), \(1\leq i\leq k\cdot(k-1)/2\), contains all vertices \(v_{\ell,j}\) where \(\{c(j),c(\ell)\}\) is the \(i\)-th color pair and \(c(\ell)>c(j)\). Now, add arcs in \(D\) as follows:  
* for level \(i\leq k\), add an arc from each vertex in level \(i\) to each vertex in level \(i+1\),
* for level \(k+2i-1\), \(1\leq i\leq k\cdot(k-1)/2\), add an arc from each vertex in level \(k+2i-1\) to its sibling in level \(k+2i\) and
* for level \(k+2i\), \(1\leq i<k\cdot(k-1)/2\), add an arc from each vertex in level \(k+2i\) to each vertex in level \(k+2i+1\). This completes the construction of \(D\). The undirected graph \(G\) is now constructed by adding the following edges:  
* for each \(w\in W\), add \(\{s,w\}\) and
* for each \(v_{i,j}\), add \(\{i,v_{i,j}\}\). Informally, the idea of the construction is to force with \(D\) that each supported path of the correct length selects exactly one vertex of each color and two vertices for each color pair. With the arcs in \(D\) between levels \(k+2i-1\) and \(k+2i\), we force that two vertices of the same color pair that are selected correspond to an edge in \(H\). Finally, with the construction of \(G\), we force that a vertex \(v_{i,j}\) of a color pair can only be selected if its endpoint \(i\) is selected. To complete the formal correctness proof of our parameterized reduction, we show the equivalence of the instances. \((H,c)\) is a yes instance if and only if there is a \((D,G)\)-supported path of length exactly \(k^{2}\). \(\Rightarrow\): Let \(S\) be a clique of order \(k\) in \(H\). Since \(c\) is a proper vertex coloring, \(S\) contains exactly one vertex of each color. Now, consider the vertex set \(V_{P}\) that contains \(\{s\}\), \(S\), and all vertices corresponding to an edge of \(H[S]\). First, note that \(|V_{P}|=1+k+2\binom{k}{2}=1+k^{2}\). Second, \(G[V_{P}]\) is connected, since \(G[S\cup\{s\}]\) is a star, and every vertex in \(V_{P}\setminus(S\cup\{s\})\) is in \(G\) a neighbor of one of its endpoints in \(V_{P}\).