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.


Hint 1. The graph doesn't have to be connected.

Hint 2. Mouse-over the following for a slightly more detailed hint.

Arrange for there to be two components. One of them has quite a long path, which you can easily find.

  • 1
    $\begingroup$ Thank you for the answer. Would the reduction still be from HAMPATH? $\endgroup$
    – Psy231
    Jun 6 '16 at 10:28
  • 1
    $\begingroup$ It would be either from that or from long-simple-path. ​ ​ $\endgroup$
    – user12859
    Jun 6 '16 at 10:35
  • $\begingroup$ I still don't know where to go from there.. What is the purpose of having two components? How do you "easily" find this path? $\endgroup$
    – Psy231
    Jun 6 '16 at 12:43
  • $\begingroup$ I'm not fishing for an answer, it's just what's hard about this problem is that I can't help but think of all possible permutations of the |V-2| nodes that must be included between s and t, and to somehow come up with a single path for the other graph, G', that incorporates these. $\endgroup$
    – Psy231
    Jun 6 '16 at 12:44

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.