LONGEST PATH is the decision problem asking if a simple path of at least $K$ edges exists in a graph $G$.

The reduction from HAMILTONIAN PATH to LONGEST PATH is pretty trivial (pass in $K = N-1$ to LONGEST PATH), and LONGEST PATH can be easily shown as NP too, so it is NP-complete.

However, I'm interested in showing NP-completeness via a direct reduction in the opposite direction (i.e. from LONGEST PATH to HAMILTONIAN PATH). One idea is to drop-out all possible combinations of $i = 1 .. N$ vertices from the original graph $G$, and run HAMILTONIAN PATH on the resultant graphs, but this would lead to $\sum_{i=1}^{N}{N \choose i} = O(4^N)$ different graphs to check, which is not a poly-time reduction.

What's a poly-time reduction in this direction which is more intuitive than reducing to 3-SAT and then reducing to HAMILTONIAN PATH?

  • $\begingroup$ @al5719 I edited this into your question, i.e., made it more direct. $\endgroup$
    – Juho
    Dec 12, 2022 at 18:51


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.