## 3 Complexity Classification for Acyclic Digraphs
: _The decision version of Longest Supported Path is NP-complete, even when \(D\) is acyclic, \(D^{*}\) is an outerplanar graph and \(G\) is a tree with diameter four._  
Proof. : The problem is clearly in NP. To show NP-hardness, we describe a reduction from MAX 2-Sat[23] (see also Figure 2 for an illustration of the reduction). Let \(\phi=C_{1}\wedge C_{2}\wedge\ldots\wedge C_{p}\) be an instance of MAX 2-Sat, built from a collection \(\mathcal{C}=\{C_{1},\ldots,C_{p}\}\) of \(p\) clauses with two literals each, over the variable set \(\mathcal{X}_{n}=\{x_{1},\ldots x_{n}\}\). Let \(D\) be built on \(2p+2n+2\) levels, called optional (marked with a star) or compulsory (not marked):  
* Level 0: a vertex \(s\);
* level\({}^{*}\)\(2i-1\), \(1\leq i\leq p\): two vertices \(v_{i,1}\) and \(v_{i,2}\) corresponding to the literals of clause \(C_{i}\);
* level \(2i\), \(1\leq i\leq p\): a vertex \(c_{i}\) corresponding to clause \(C_{i}\);
* level \(2p+1\): two vertices \(v_{p+1,1}\) and \(v_{p+1,2}\) corresponding, respectively, to literals \(x_{n}\) and \(\overline{x_{n}}\);
* level \(2p+2\): a vertex \(c_{p+1}\);
* level \(2p+2+2i-1\), \(1\leq i\leq n\): two vertices \(a_{i}\) and \(b_{i}\);
* level \(2p+2+2i\), \(1\leq i<n\): a vertex \(A_{i}\). Then, add (a) all possible arcs between any two consecutive levels, (b) the arc \((s,c_{1})\) and (c) the arcs \((c_{i},c_{i+1}),1\leq i<p\). It is clear that \(D\) is a DAG. To see that \(D^{*}\) is an outerplanar graph, it is sufficient to  
Figure 2: Construction of \(D\) and \(G\) from the following instance of MAX 2-Sat with \(p=2\) and \(n=3\): \(\phi=(x_{1}\lor x_{3})\wedge(\overline{x_{1}}\lor x_{2})\). Levels in \(D\) are represented from left to right. The orange vertices form the \((D,G)\)-supported path corresponding to the assignment \(\{x_{1}=\mathrm{true},x_{2}=\mathrm{false},x_{3}=\mathrm{true}\}\). draw the vertices on a circle according to the order \(s,v_{1,1},c_{1},v_{2,1},c_{2},\ldots,v_{p+1,1}\), \(c_{p+1}\), \(a_{1}\), \(A_{1},\ldots,a_{n-1}\), \(A_{n-1},a_{n},b_{n},\ldots,b_{1},v_{p+1,2},\ldots,v_{1,2}\). Graph \(G\) is a tree with root \(s\). There is an edge between \(s\) and each vertex in \(\{a_{i},b_{i}:1\leq i\leq n\}\cup\{A_{i}:1\leq i<n\}\cup\{c_{i}:1\leq i\leq p+1\}\). There is an edge between each vertex \(a_{i}\) (resp. \(b_{i}\)) and any vertex \(v_{\ell,m}\) with \(1\leq\ell\leq p+1,1\leq m\leq 2\), such that \(v_{\ell,m}\) corresponds to the literal \(x_{i}\) (resp. \(\overline{x_{i}}\)). Figure 2 is an illustration of the reduction described above, with \(\phi=(x_{1}\lor x_{3})\wedge(\overline{x_{1}}\lor x_{2})\). Notice that \(G\) is of diameter four, where \(s\) plays a central role. We now claim that there is an assignment for the variables in \(\mathcal{X}_{n}\) that satisfies at least \(k\) clauses if and only if there is a \((D,G)\)-supported path of length at least \(p+k+1+2n\). \(\Rightarrow\): Let \(\mathcal{A}\) be an assignment of the variable set \(\mathcal{X}_{n}\) that satisfies \(k^{\prime}\) clauses \(C_{i_{1}},\ldots,C_{i_{k^{\prime}}}\) of \(\mathcal{C}\), where \(k^{\prime}\geq k\). Assume without loss of generality that vertices \(v_{i_{1},1},\ldots,v_{i_{k^{\prime}},1}\), \(v_{p+1,1}\) correspond to true literals. Let \(\mathcal{B}(i)=a_{i}\) if \(x_{i}\) is true, and \(\mathcal{B}(i)=b_{i}\) otherwise. Then, the path \(P\) with vertices \(s,v_{i_{1},1},\ldots,v_{i_{k^{\prime}},1},v_{p+1,1},c_{1},\ldots\), \(c_{p+1},\mathcal{B}(1),A_{1},\mathcal{B}(2),A_{2},\ldots,\mathcal{B}(n-1),A_{ n-1},\mathcal{B}(n)\) is \((D,G)\)-supported and has length \(p+k^{\prime}+1+2n\). Indeed, in \(G\), the vertices \(v_{i_{1},1},\ldots,v_{i_{k^{\prime}},1},v_{p+1,1}\) are connected to \(s\) using the corresponding vertex \(\mathcal{B}(\ell_{i_{j}})\) (where \(v_{i_{j},1}\) is \(x_{\ell_{l_{j}}}\) or \(\overline{x_{\ell_{l_{j}}}}\)), \(1\leq j\leq k^{\prime}\) and \(\mathcal{B}(n)\), respectively. All of the other vertices are adjacent to \(s\).