## 3 Complexity Classification for Acyclic Digraphs  
In this section, we continue our complexity analysis for the special case where \(D\) is acyclic. First, we identify some special cases in which all three problems can be solved in polynomial time. **Proposition 2**. : _If \(D\) is acyclic, then Longest Supported Path and Shortest Supported Path can be:_  
1. _solved in polynomial time if_ \(D^{*}\) _is a tree,_
2. _solved in polynomial time if_ \(G\) _is a chordless path or cycle or_
3. _solved in_ \(2^{k}\cdot n^{O(1)}\) _time if_ \(G\) _has at most_ \(k\) _vertices with degree two or more._  
Proof. : Before studying each case, we note that, in a DAG, the longest path, as well as the longest path between two given vertices can be computed in linear time, using dynamic programming. 1. Since \(D^{*}\) is a tree, the set \(\mathcal{P}\) of (directed) paths in \(D\) can be computed in polynomial time: there is at most one path between every pair of vertices in \(D\), and if it exists, it can be found in linear time for each pair of endpoints. Hence, the longest and the shortest \((D,G)\)-supported path can be found as follows. Check for each pair of endpoints \(u\) and \(v\) whether there is a path \(P\) between \(u\) and \(v\) in \(D\). If this is the case, check whether \(G[P]\) is connected. If this is the case, keep \(P\) if it is longer or shorter than the currently stored shortest or longest paths. 2. Since \(G\) is a path or a cycle, the number of connected subgraphs of \(G\) is \(O(n^{2})\), and they may be computed in polynomial time. Further, for each connected subgraph \(G^{\prime}=(V^{\prime},E^{\prime})\) of them, one can compute in linear time whether \(D[V^{\prime}]\) has a Hamiltonian path, because \(D\) is acyclic. The longest (resp. shortest) \((D,G)\)-supported path is the maximum-order (resp. minimum-order) subgraph \(G^{\prime}\) of \(G\) for which this is the case. 3. Let \(X\) denote the set of \(k\) vertices with degree two or more in \(G\). For each \(X^{\prime}\subseteq X\), we solve the problem of finding a \((D,G)\)-supported path that contains \(X^{\prime}\) as follows. Clearly, we only need to consider \(X^{\prime}\), such that \(G[X^{\prime}]\) is connected. Further, we can remove from \(G\) all degree-one vertices that have no neighbor in \(X^{\prime}\). Let \(Y\) denote the set of remaining degree-one vertices, and note that \(G[X^{\prime}\cup Y^{\prime}]\) is connected for all \(Y^{\prime}\subseteq Y\). Hence, it is sufficient to compute the longest (resp. shortest) path in \(D[X^{\prime}\cup Y]\) that contains all vertices of \(X^{\prime}\). Fix an arbitrary topological ordering of \(D[X^{\prime}\cup Y]\). Then, the order \((x_{1},x_{2},\ldots,x_{|X^{\prime}|})\) of the vertices of \(X^{\prime}\) in this topological ordering determines the order of the vertices of \(D[X^{\prime}\cup Y]\) in any path that contains \(X^{\prime}\): by definition of topological orderings, there is no directed path from \(x_{i+1}\) to \(x_{i}\), so \(x_{i+1}\) must be after \(x_{i}\) in such a path. By the same argument, for each \(x_{i}\), \(1\leq i<|X^{\prime}|\), any path between \(x_{i}\) and \(x_{i+1}\) contains only vertices that are put between \(x_{i}\) and \(x_{i+1}\) by this topological ordering. Hence, the longest (resp. shortest) path that contains \(X^{\prime}\) in this graph can be computed by concatenating the longest (resp. shortest) paths between \(x_{i}\) and \(x_{i+1}\) for all \(i\), \(1\leq i<|X^{\prime}|\). As discussed above, each such path can be computed in polynomial time. Hence, the overall running time is \(2^{k}\cdot n^{O(1)}\)Note that Case (c) includes the cases in which \(G\) is a star or a bi-star, that is, all trees with diameter at most three. To extend these tractability results, one might try, for example, to achieve polynomial-time algorithms for the case that \(D^{*}\) and \(G\) have bounded treewidth or for the case that \(G\) has diameter four. The theorem below, however, shows that Longest Supported Path becomes NP-hard in these cases. **Theorem 3**.