Optimal Path in a Graph with Node and Edge Weights

user_1970053 0
Viewed 123

Consider the following Directed graph with Node and Edge Weights. A bidigraph

Is there a non NP-Hard algorithm to find out the path of maximal score, where

score = sum(node weights) - sum(edge weights)

For the example graph, maximal score path is along path A -> B -> C -> D. Maximal score being 164 ((77 + 27 + 32 + 84) - (44 + 12 + 0)).

np graph-theory complexity-theory algorithm
1 Answers

I think that there isn't any algorithm that can find the solution in polynomial time, I'm trying to prove that this problem is NP-Hard because we can reduce it to the longest path problem and the longest path problem can be reduced to it.

Here's my attempt (assuming that both edge and node weights are positive):

  1. Reduction from this problem to the longest path problem:

This problem can be reduced to the longest path problem by splitting each node A into two nodes A-IN and A-OUT, such that these nodes doesn't have any weights, we link incoming edges to A into A-IN, and outgoing edges from A to A-OUT, and add an edge between A-IN and A-OUT with weight equal to -1 times node A's original weight. Now to find a solution to the problem you have to find the longest path in this graph.

  1. Reduction from the longest path problem to this problem (and here I'm not sure that I didn't do any mistakes):

The longest path problem can be reduced to this problem by taking each negative weight edge E between two nodes A and B and create a virtual node AB in the middle of it, we remove E from the graph then add an edge from A to AB with weight 0, and an edge from AB to B with weight 0, and give node AB weight equal to -1 times the weight of the original E.

So that was hopefully a proof that you can solve the longest path problem by reducing it to your problem, so if there is a polynomial time solution to your problem then P = NP.

user_181593340
Related