This assignment continues to explore NP-Completeness and NP-Complete problems. Homework Problems 1. Undirected Hamiltonian Paths (12 pts) 2. Hamiltonian Cycles (12 pts) 3. Making Hamiltonian Paths (11 pts) 4. README (1 point) Total: 36 points Submitting Submit your solution to this assignment in Gradescope hw12. Please assign each page to the correct problem and make sure your solutions are legible. A submission must also include a README containing the required information. 1 Undirected Hamiltonian Paths Prove that UHAMPATH (from lecture) is NP-Complete. Start with the ideas from class. Make sure to include all the required parts of the proof as described in lecture. 2 Hamiltonian Cycles Recall that a cycle in a graph (see Sipser Ch 0) is a path that starts and ends at the same vertex. Also, a Hamiltonian path is a path that touches every vertex in the graph. Prove that the following language is NP-Complete. HCYCLE={G|G is a directed graph with a Hamiltonian cycle} Make sure to include all the required parts of the proof. 3 Making Hamiltonian Paths Recall that a Hamiltonian path is a path that touches every vertex in the graph. Prove that the following language is NP-Complete. HMAKE={?G,k?|G is a directed graph that has a Hamiltonian path if k edges are added to it} Make sure to include all the required parts of the proof.
Comments