## NP-Completeness – Global Homework Experts

This assignment continues to explore NP-Completeness and NP-Complete problems.

**Homework Problems**

- Undirected Hamiltonian Paths(12 pts)
- Hamiltonian Cycles(12 pts)
- Making Hamiltonian Paths(11 pts)
- 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 are closed.