Consider the Hamiltonian Path Problem we discussed in our

lecture notes. You are required to provide a detailed argument demonstrating that the

problem is NP$-$complete. This should include showing that the Hamiltonian Path Prob$-$

lem is in NP and providing a polynomial reduction from a known NP$-$hard problem.

Hints: Your argument should focus on reducing a known NP$-$hard problem $($refer to

one of the problems discussed in our lecture notes$)$ to the problem you have selected.

$($a$)(2$ points$)$ Please write the definition of the Hamiltonian Path Problem along with

the definition of a known NP$-$hard problem.

$($b$)(2$ points$)$ Please show that the Hamiltonian Path Problem is in NP$.$

$($c$)(4$ points$)$ Please write the polynomial reduction process.