## 3 Complexity Classification for Acyclic Digraphs
\(\Leftarrow\): Let \(P\) be a \((D,G)\)-supported path \(P\) of length at least \(p+k+1+2n\), _i.e._, with at least \(p+k+2n+2\) vertices. Now, there are at most \(p+2+2n\) compulsory levels implying that \(P\) contains at least \(k\) vertices from optional levels. As \(P\) cannot contain two vertices associated with literals \(x_{i},\overline{x_{i}}\) for some \(i\) (because at most one of the vertices \(a_{i}\) and \(b_{i}\), needed for the connection in \(G\), belong to \(P\)), we may safely assign the value \(true\) to the literals associated with the vertices in \(P\) on optional levels. These literals yield a correct assignment that satisfies \(k\) clauses. \(\Box\)  
The above reduction shows hardness for Longest Supported Path. By slightly extending the class of graphs for \(D^{*}\), we can also show hardness for Supported Path and, thus, also for Shortest Supported Path, even if \(D\) is acyclic. This reduction also implies that Longest Supported Path is not \(f\)-approximable, for any function \(f\), even if \(D\) is acyclic. **Theorem 4**. : Supported Path _is NP-complete even when \(G\) is a tree of diameter four, and the underlying undirected graph \(D^{*}\) of \(D\) has treewidth three._  
Proof. : The proof is by a reduction from 3-SAT. Let \(\phi\) be a Boolean formula with clauses \(C_{i}=(l_{i,1},l_{i,2},l_{i,3})\), \(1\leq i\leq p\) over the set of variables \(\mathcal{X}_{n}=\{x_{1},x_{2},\ldots,x_{n}\}\). Assume that \(C_{p}=(x_{n},x_{n},x_{n})\) (this can be achieved by adding one variable and one clause to the input formula \(\phi\)). We now describe how to build \(D\) and \(G\) from \(\phi\). The directed acyclic graph \(D\) is built on \(p+n+1\) levels, numbered from zero to \(p+n\). Each level contains between one and three vertices:  
1. Level 0: one vertex \(s\),
2. level \(i\), \(1\leq i\leq p\): three vertices \(l_{i,1},l_{i,2},l_{i,3}\) that correspond to the variables occurring in clause \(C_{i}\),
3. level \(p+j\), \(1\leq j\leq n\): two vertices \(a_{j}\) and \(b_{j}\). We complete the construction of \(D\) by adding all arcs from any vertex on level \(i\) to any vertex on level \(i+1\), for all \(0\leq i<p+n\). The undirected graph \(G\) has the same vertex set as \(D\). We define \(X_{j}\) (resp. \(\overline{X_{j}}\)) to be the set of vertices in \(V(G)\) such that the literal corresponding to this vertex is \(x_{j}\) (resp. \(\overline{x_{j}}\)), for all \(1\leq j\leq n\). The edges of \(G\) are obtained as follows:1. put an edge between each vertex in \(X_{j}\) and vertex \(a_{j}\)
2. put an edge between each vertex in \(\overline{X_{j}}\) and vertex \(b_{j}\)
3. put an edge \(\{s,a\}\) for each \(a_{i}\) and an edge \(\{s,b\}\) for each \(b_{i}\)  
Figure 3 gives an illustration of the above reduction. Notice that \(G\) is a tree of diameter four, in which \(s\) plays a central role. Note also that \(D^{*}\) has treewidth three, since each level consists of three vertices, and all arcs are between consecutive levels. It remains to show the equivalence of the instances, which is formalized as follows: \(\phi\) is satisfiable if and only if there is a \((D,G)\)-supported path of length at least one. \(\Rightarrow\): Let \(\mathcal{A}\) be an assignment of the variables \(x_{1},\ldots,x_{n}\) that satisfy \(\phi\). Consider a path \(P\) in \(D\) that contains \(s\) and for each level \(i\), \(1\leq i\leq p\), one (arbitrary) vertex that corresponds to a literal that is set to true by \(\mathcal{A}\), and for each level \(i\), \(p<i\leq p+n\), the vertex \(a_{i}\) if \(\mathcal{A}\) assigns true to \(x_{i}\) and the vertex \(b_{i}\), otherwise. We now show that \(G[V(P)]\) is connected, which implies that \(P\) is a \((D,G)\)-supported path of length at least one. First, each vertex \(a_{i}\) or \(b_{i}\) is adjacent to \(s\), so the subgraph of \(G[V(P)]\) induced by \(s\) plus the vertices from levels \(i>p\) is connected.