HAMILTONIAN PATH PROBLEM: given a directed graph, does it contain a path that st

Question

HAMILTONIAN PATH PROBLEM: given a directed graph, does it contain a path that starts at some vertex and goes to some other vertex, going through each remaining vertex exactly once. HAMILTONIAN CYCLE PROBLEM: given a directed simple graph, does it contain a directed simple cycle that goes through each vertex exactly once. Assume that the HAMILTONIAN PATH PROBLEM is known to be NP-complete. Given this assumption, prove that the HAMILTONIAN CYCLE PROBLEM is NP-complete for directed graphs. (Show that the HAMILTONIAN CYCLE PROBLEM is in NP, and is also NP-hard.)

Explanation / Answer

Language is NP if a proposed solution can be verified in poly time.

So for Hamiltonian Cycle - proposed solution/certificate is a list of vertex in order tem appear in claimed cycle.

To verify this is solution count vertice in solution and count vertice of graph, if they mismatch return False

After that check if all given vertices are connected by edge in order and last is conneted to first, if not return false.

This takes time polynomial to n because there are n vertices to count and n edges to check, n is a polynomial so this runs in poly time.

This shows Hamiltonian Cycle is in NP.

Now lets reduce Hamiltonian cycle to Hamiltonian path.

If we have solution to Hamiltonian cycle then we just need to remove edge from last to first to get hamiltonian path

As Hamiltonian path is NP-complete, Hamiltonian cycle is also NP complete.

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.