Shortest simple path with minimum edge cost minus node reward

Question

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.

Follow-up:

Please see this post for a "proof" which gave me the (wrong) hint.

Answer 1

As we discussed earlier, this can be solved by transforming your weighted edges-and-nodes graph to a normal weighted-edges graph: simply make the edge-weights in the new graph equal to the edge-weights in the old graph minus the reward of the node they point to. This may lead to a graph with negative-cycles; and finding a simple path on such a graph is NP-Hard.

Unfortunately, the two problems are equivalent. The transformation in the other direction is easy - given a directed weighted graph with negative cycles, you can turn it into a directed weighted-edges-and-nodes graph with no negative edges simply by setting the "reward" of each node to the lowest incoming edge, and subtracting that amount from all incoming edges.

Thus, your problem NP-Hard in the general case. However, the sub-cases where the transformation in the first paragraph would generate a graph with no negative edge-cycles (ex. if, for instance, the node's reward is <= the least weight of an incoming edge) are in P.