The problem is as follows:Given a weighted graph G and a path p, show that p is the longest simple path in G.I'm thinking a reduction from HAMPATH would work, but after 3 hours of racking my brain over this, I have no idea how to do it. What makes the reduction difficult is that I'd need to somehow know the path, since the input to this longest path variant requires the path along with the graph.Any tips/hints/help would be appreciated.
How do I show this variant of the longest path problem is NP-hard?
complexity theory;np complete