Longest path on directed acyclic graph when the weight is defined on the pair of edges Given a directed acyclic graph $G=(V,E)$ with a source node $s$ and a sink node $t$, and we have a weight function that is defined on $E\times E$, $f:E\times E\to R^{+}$. We want to find a $s$-$t$ path $P$ that maximizes the sum $\sum_{\forall e_i,e_j\in P} f(e_i,e_j)$.
Does this problem have a polynomial solution?
 A: The quadratic shortest path problem (QSSP) can be reduced to the problem. Because QSSP is NP-hard [1], the problem in the question has no polynomial-time solution unless P = NP.
To remove the restriction of the acyclicity of the graph, we can use the standard technique of using $V \times \{0,\dots,|V|\}$ as the new vertex space where the integer in a pair represents the length of the current path, so an edge $(u,v)$ is converted to $((u,k), (v,k+1))$.
Furthermore, by adding edges $((t,k), (t,k+1))$ corresponding a loop at the destination, we ensure all paths have the same path length.
To convert the minimization problem to the maximization problem, let $W$ be a number larger than all weights and then convert weights as $W - f(e_1,e_2)$. Because all paths have the same length in the new graph, the ordering of the solutions is exactly reversed.

*

*[1] Rostami, Borzou, et al. "On the quadratic shortest path problem." International Symposium on Experimental Algorithms. Springer, Cham, 2015. https://hal.inria.fr/hal-01251438/file/QSPPaperHal.pdf.

