A variation of longest paths in directed acyclic graph 
Let $D=(V,A)$ be a simple directed acyclic graph, where $A$ is a set of arcs. Let $S$ be a subset of $\{(u,v)| \text{there is a directed path from $u$ to $v$}\}$. The $S$-length of a path $P$ is defined to be the number of elements of $S$ contained in $P$, here $(u,v)\in S$ is said to be contained in $P$ if $u,v \in V(P)$. For example, if $S =\{(u,v)| \text{there is a directed path from $u$ to $v$}\}$, then length of a path $P$ is ${L(P)}\choose{2}$ where $L(P)$ is the length of the path $P$. My question is to find a path of longest $S$-length in $D$. Is there a polynomial algorithm to solve it? If it is NP-hard, then is there a good approximation algorithm?

I am so sorry I realized there is a mistake in my old question. Here $S$ is a subset of $V\times V$,i.e, a subset of all pairs of vertices, but $S$ is not a subset of $A$. 
 A: It’s NP-hard to approximate this within any constant factor, by a reduction from 2-CSP (that it is hard to approximate 2-CSP follows from the PCP theorem and parallel repetition). Suppose I have an instance of 2-CSP with variables $x_1, ..., x_n$ taking values in the alphabet $\Sigma$, and constraints $C_{i,j} \subseteq \Sigma \times \Sigma$ for certain pairs $i,j$ between $1$ and $n$. Make a directed graph $(V, A)$ with $V = \{v_{i,a} : i \le n, a \in \Sigma\}$ and $A = \{(v_{i,a}, v_{i+1,b}) : i \le n-1, a,b \in \Sigma\}$. For each constraint $C_{i,j}$ (assuming $i$ less than $j$ without loss of generality), we include the pairs $(v_{i,a},v_{j,b})$ such that $(a,b) \in C_{i,j}$ in the set $S$. Then any maximal path corresponds to an assignment of the variables to elements of $\Sigma$, and the $S$-length is equal to the number of satisfied constraints.
A: The wikipedia page on longest path problems gives an efficient algorithm to find longest paths in directed acyclic graphs:
https://en.wikipedia.org/wiki/Longest_path_problem
If you adapt this algorithm by weighting arcs 1 if they lie in S, and 0 otherwise, this gives the algorithm you want.
