Please answer each question and show your work.

A hamiltonian path in a graph is a simple path that visits every vertex exactly once. Consider the language HAM-PATH = {G. u, u) : there is a hamiltonian path from u to u in graph G). Show that HAM-PATH E (a) (l5pts) Given an instance (G, u, v) of a problem that contains a hamiltonian path from u to u, describe (b) (15pts) Give a polynomial-time verification algorithm that would use the above certificate to verify Now that we know that HAM-PATH E NP, there is one more step remaining to prove that the Hamil- (c) (10pts) What would you have to do to prove that Hamiltonian path problem is NP-complete. Simply NP as follows: what the certificate would look like. that the instance indeed has a hamiltonian path. tonian path problem is NP-complete. identify what you would have to do, you don't actually have to do it for this homework. A hamiltonian path in a graph is a simple path that visits every vertex exactly once. Consider the language HAM-PATH = {G. u, u) : there is a hamiltonian path from u to u in graph G). Show that HAM-PATH E (a) (l5pts) Given an instance (G, u, v) of a problem that contains a hamiltonian path from u to u, describe (b) (15pts) Give a polynomial-time verification algorithm that would use the above certificate to verify Now that we know that HAM-PATH E NP, there is one more step remaining to prove that the Hamil- (c) (10pts) What would you have to do to prove that Hamiltonian path problem is NP-complete. Simply NP as follows: what the certificate would look like. that the instance indeed has a hamiltonian path. tonian path problem is NP-complete. identify what you would have to do, you don't actually have to do it for this