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?



Longest path on directed acyclic graph when the weight is defined on the pair of edges
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>.


