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.

  • 1
    $\begingroup$ Could you please elaborate a little bit more on those hints from submodular analysis? Maybe just providing some references could help $\endgroup$ – Carlos Linares López Oct 22 '13 at 21:56
  • $\begingroup$ Hi Carlos, I detailed a "proof" here that misled me. Now I see where I got wrong. $\endgroup$ – Janathan Oct 23 '13 at 15:35
  • $\begingroup$ 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. $\endgroup$ – Carlos Linares López Oct 24 '13 at 0:23

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.

  • 1
    $\begingroup$ Thank you very much again, Danny. I detailed a "proof" here that misled me. Now I see where I got wrong. $\endgroup$ – Janathan Oct 23 '13 at 15:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.