0
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ Thank you for the answer. Would the reduction still be from HAMPATH? $\endgroup$
    – Psy231
    Jun 6, 2016 at 10:28
  • 1
    $\begingroup$ It would be either from that or from long-simple-path. ​ ​ $\endgroup$
    – user12859
    Jun 6, 2016 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, 2016 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, 2016 at 12:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.