I am wondering whether the Shortest Hamiltonian Path (SHP) problem is NP-Complete, because I couldn't find a way of solving it in a polynominal time. if it is NP_Complete, it will be so kind of you to give me the proof or the relevent papers,thanks a lot

the problem explanation: Given a directed,weighted graph with n vertices, find the shortest hamiltonian path with end vertices v and u. by the way,the graph must exit a hamiltonian path from v to u.

  • 1
    $\begingroup$ It is easy to reduce this problem to not-returning-to-starting-city variant of travelling salesman problem, or to Hamiltonian path problem. $\endgroup$ – xskxzr Mar 8 '18 at 11:30
  • 1
    $\begingroup$ It's not clear what you mean by "the graph must exit a hamiltonian path from v to u". Do you mean that the algorithm must output a path? $\endgroup$ – Pål GD Mar 8 '18 at 15:33
  • 1
    $\begingroup$ @j_random_hacker The edges have weights, so I think the smallest total weight of the edges in the path is meant. $\endgroup$ – Discrete lizard Mar 8 '18 at 17:38
  • $\begingroup$ @Discretelizard: Thanks, I completely missed that! $\endgroup$ – j_random_hacker Mar 8 '18 at 17:41

Here's a small hint.

Let $G$ be a directed graph with unit weights, and $u$ and $v$ be two vertices. Suppose that I could solve SHP in polynomial time, say, $O(n^c)$.

Now, say that I would like to solve Hamiltonian Path on a directed graph. Let me spend $O(n^2)$ time to "guess" your vertices $u$ and $v$, and for each of them run your algorithm for SHP. Then, I would in $O(n^{c+2})$ time have either found a Hamiltonian path in $G$, or conclude that $G$ is not Hamiltonian.

That would mean that P = NP.

Now, this doesn't prove that your problem in NP-complete. For that, you need to come up with a reduction. But it does tell you that you should probably not spend too much time looking for a polynomial time algorithm.

| cite | improve this answer | |

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.