# 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?

• Polynomial in what? Commented Jun 16, 2022 at 23:34
• polynomial in number of vertices
– cbyh
Commented Jun 17, 2022 at 0:54

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.