NP-Completeness – Global Homework Experts

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

order now

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={GG 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.