I have a directed graph which has cycles. Each edge has a nonnegative weight and each vertex has a nonnegative reward.
Given two vertices s and t, I need to find a simple path (a path with no repeated vertices) from s to t which minimizes
(sum of edge weights on the path) - (sum of vertex rewards covered by the path).
One can surely absorb node reward into edge weight like this post, but then the edge weight can become negative and negative cycles can emerge. As a result, the shortest simple path, if posed in such a general setting, is NP-hard (eg this post).
However, some hints from submodular analysis suggest this problem is not NP-hard. Can we find an efficient algorithm?
Many thanks in advance.
Please see this post for a "proof" which gave me the (wrong) hint.