2
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ Polynomial in what? $\endgroup$
    – LSpice
    Commented Jun 16, 2022 at 23:34
  • 1
    $\begingroup$ polynomial in number of vertices $\endgroup$
    – cbyh
    Commented Jun 17, 2022 at 0:54

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .