# Reduction from LONGEST PATH to HAMILTONIAN PATH

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?

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