<p>As <a href="https://stackoverflow.com/questions/19520672/shortest-acyclic-path-on-directed-cyclic-graph-with-negative-weights-cycles/19521656#comment28962941_19521656">we discussed earlier</a>, 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 <a href="https://cstheory.stackexchange.com/questions/17462">is NP-Hard</a>.</p>

<p>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.</p>

<p>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 <em>(ex. if, for instance, the node's reward is &lt;= the least weight of an incoming edge)</em> are in P.</p>

CC BY-SA 3.0
2013-10-23T15:36:06.590Z
Thank you very much again, Danny.  I detailed a "proof" [here](http://cstheory.stackexchange.com/questions/19494/whats-wrong-with-my-linear-programming-formulation-of-longest-path) that misled me. Now I see where I got wrong.
Janathan
CC BY-SA 3.0
2013-10-22T18:19:03.763Z
2013-10-22T20:41:49.270Z
2017-05-23T12:40:09.333Z
BlueRaja - Danny Pflughoeft
<p>I have a directed graph which has cycles. 
Each edge has a nonnegative weight and each vertex has a nonnegative reward.</p>

<p>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 </p>

<p>(sum of edge weights on the path) - (sum of vertex rewards covered by the path). </p>

<p>One can surely absorb node reward into edge weight like <a href="https://cstheory.stackexchange.com/questions/16226/finding-a-minimum-node-weight-path">this post</a>, 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 <a href="https://cstheory.stackexchange.com/questions/17462/finding-the-shortest-path-in-the-presence-of-negative-cycles">this post</a>).</p>

<p>However, some hints from submodular analysis suggest this problem is not NP-hard. Can we find an efficient algorithm?</p>

<p>Many thanks in advance.</p>

<p><strong>Follow-up</strong>:</p>

<p>Please see <a href="https://cstheory.stackexchange.com/questions/19494/whats-wrong-with-my-linear-programming-formulation-of-longest-path">this post</a> for a "proof" which gave me the (wrong) hint.</p>

CC BY-SA 3.0
2013-10-22T21:56:34.697Z
Could you please elaborate a little bit more on those hints from submodular analysis? Maybe just providing some references could help
Carlos Linares López
CC BY-SA 3.0
2013-10-23T15:35:21.977Z
Hi Carlos, I detailed a "proof" [here](http://cstheory.stackexchange.com/questions/19494/whats-wrong-with-my-linear-programming-formulation-of-longest-path) that misled me. Now I see where I got wrong.
Janathan
CC BY-SA 3.0
2013-10-24T00:23:47.880Z
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.
Carlos Linares López
<graph-algorithms><shortest-path>
Shortest simple path with minimum edge cost minus node reward
Janathan
# Shortest simple path with minimum edge cost minus node reward

(Asked by: username_0 on 2013-10-22)

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](https://cstheory.stackexchange.com/questions/16226/finding-a-minimum-node-weight-path), 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](https://cstheory.stackexchange.com/questions/17462/finding-the-shortest-path-in-the-presence-of-negative-cycles)).

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](https://cstheory.stackexchange.com/questions/19494/whats-wrong-with-my-linear-programming-formulation-of-longest-path) for a "proof" which gave me the (wrong) hint.

**Tags:** graph-algorithms, shortest-path

> **Comments:**
> **username_1**: Could you please elaborate a little bit more on those hints from submodular analysis? Maybe just providing some references could help  
> **username_0**: Hi Carlos, I detailed a "proof" [here](http://cstheory.stackexchange.com/questions/19494/whats-wrong-with-my-linear-programming-formulation-of-longest-path) that misled me. Now I see where I got wrong.  
> **username_1**: Hey username_0, 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.  

---

## 1 answers

### Answer by username_2 on 2013-10-22. Score: 1 | Accepted answer

As [we discussed earlier](https://stackoverflow.com/questions/19520672/shortest-acyclic-path-on-directed-cyclic-graph-with-negative-weights-cycles/19521656#comment28962941_19521656), 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](https://cstheory.stackexchange.com/questions/17462).

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.

> **Comments:**
> **username_0**: Thank you very much again, Danny.  I detailed a "proof" [here](http://cstheory.stackexchange.com/questions/19494/whats-wrong-with-my-linear-programming-formulation-of-longest-path) that misled me. Now I see where I got wrong.  

---

