CODEWITHSUNDEEP
algorithm
Bombyx mori
Bombyx mori

Reputation: 288

Why cannot we turn longest path into shortest graph?

Today I read on Introduction to Algorithms of the longest path problem, which asked in a weighted, directed graph what is the longest simple path passing two vertices. The author used a wonderful example showing that dynamic programming fails for the longest path problem because there does not exist a nice optimal structure that always comes with an optimal substructure. It was commented that this problem is actually NP-complete. So it must be really hard.

Now here is my question: Instead of assign every edge a positive weight k>0, what if we simply assign negative weights to each edge with weight-k? Then each "longest path" would automatically be the shortest path, and if there is no loops in the shortest path by definition, there should not be any loops in the corresponding longest path. Hence using a quite common trick we "can" turn the longest path problem into the shortest path problem.

Can someone point out my mistake in the reasoning? I figure something must be wrong but do not really know what it is. It is extremely unlikely my argument is correct, for obvious reasons. Reading the pseudo code provided in the book, it seems the algorithm for shortest path does not prohibit using negative weights, and after all everything can be "elevated" by adding a large enough constant to make them positive. I am a beginner in algorithms so this question might be trivial to experts.

Upvotes: 0

Views: 2579

Answers (2)

philipxy
philipxy

Reputation: 15118

if there is no loops in the shortest path by definition, there should not be any loops in the corresponding longest path

...and so that particular original problem is solvable in polynomial time. And if the particular original problem is a DAG then this method solves it in linear time.

The complexity statement doesn't say that all graphs are that hard to solve, just that some are.

From your own link:

In contrast to the shortest path problem, which can be solved in polynomial time in graphs without negative-weight cycles, the longest path problem is NP-hard, meaning that it cannot be solved in polynomial time for arbitrary graphs unless P = NP.

[...]

For most graphs, this transformation is not useful because it creates cycles of negative length in −G. But if G is a directed acyclic graph, then no negative cycles can be created, and longest paths in G can be found in linear time by applying a linear time algorithm for shortest paths in −G, which is also a directed acyclic graph.

Upvotes: 0

templatetypedef
templatetypedef

Reputation: 372804

The mistake in your reasoning is this line:

if there is no loops in the shortest path by definition, there should not be any loops in the corresponding longest path.

If you have a graph where all edges have negative weight (which can happen in the transformation you're describing) and there's a negative cycle, then there is no shortest path between any two nodes on that cycle, since any path between them can have its cost reduced by following the cycle more and more times. Since there is no shortest path in that case, your reasoning breaks down.

Now, you can argue that you should instead look for the shortest simple path between the nodes (that is, a path with no duplicated edges). Unfortunately, though, that problem is also NP-hard, so this reduction doesn't actually buy you anything.

Hope this helps!

Upvotes: 1

Related Questions