1
$\begingroup$

I know how to prove longest-path problem by reducing Hamiltonian Path problem.

Here I want to prove NP-hardness of a Hamiltonion Path problem by reducing longest-path problem. (pretend we know longest-path problem is NP-hardness, not Hamiltonion Path problem)

I'm wondering if it is possible to reduce Hamiltonian Path problem to longest path problem.

Is there any way I can do that?

$\endgroup$
1
3
$\begingroup$

Suppose you have a graph $G$ of order $n$. $G$ has a simple path of length $\geq n - 1$ if and only if $G$ has a hamiltonian path.

$\endgroup$
3
  • $\begingroup$ why it has to be a simple path? $\endgroup$ – musk May 12 at 16:18
  • $\begingroup$ Because the longest path problem is defined only for simple paths. $\endgroup$ – Nathaniel May 12 at 16:19
  • $\begingroup$ @musk If a path is not simple then you can move to and fro on an edge infinite times. The longest path would trivially be infinite. $\endgroup$ – Inuyasha Yagami May 12 at 17:42

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.