# Shortest simple path with minimum edge cost minus node reward

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?

Follow-up:

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

• Could you please elaborate a little bit more on those hints from submodular analysis? Maybe just providing some references could help Oct 22, 2013 at 21:56
• Hi Carlos, I detailed a "proof" here that misled me. Now I see where I got wrong. Oct 23, 2013 at 15:35
• Hey Janathan, thanks for posting that. I am sorry that it got -3 points. I upvoted since I acknowledge that effort in providing a clarification to this question. Jeffe's answer is right you are not forcing your linear program to consist of connected collection of edges. Oct 24, 2013 at 0:23