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.