Hamiltonian Cycle Problem Computer Science Engineering (CSE) Notes | EduRev

Theory of Computation

Computer Science Engineering (CSE) : Hamiltonian Cycle Problem Computer Science Engineering (CSE) Notes | EduRev

The document Hamiltonian Cycle Problem Computer Science Engineering (CSE) Notes | EduRev is a part of the Computer Science Engineering (CSE) Course Theory of Computation.
All you need of Computer Science Engineering (CSE) at this link: Computer Science Engineering (CSE)

Part VII. Hamiltonian Cycle Problem

11 Hamiltonian Cycle Problem

Hamiltonian Cycle
A hamiltonian cycle in an undirected graph is a simple cycle which contains every vertex of the graph.
A graph which contains a hamiltonian cycle is called hamiltonian. A graph which does not contain a hamiltonian cycle is called nonhamiltonian.
Example:
Consider the following graph:
Hamiltonian Cycle Problem Computer Science Engineering (CSE) Notes | EduRev
Note that the hamiltonian cycle path passes through every vertex.

Hamiltonian Cycle Problem
The hamiltonian cycle problem is to check whether a graph has a hamiltonian cycle..

Hamiltonian Cycle Problem is NP-Complete
We know that a problem is in class NP-Complete if: it is in NP and it is NP Hard.

Theorem:
Hamiltonian cycle problem is NP-complete.

Proof:

Step 1: Prove that hamiltonian cycle problem is in class NP.
A set with n elements has 2n possible subsets. Then a graph with n vertices has 2n possible permutations of vertices.So an algorithm needs to check whether any one of these permutation form a hamiltonian path. If the graph is represented as an adjacency matrix, it will take n! comparisons. It has worst case time complexity Θ(2√n). (not polynomial time, but exponential time).
Let we are given a graph and a ’certificate’ telling that a sequence of vertices form a hamiltonian cycle. An algorithm can verify whether this path is hamiltonian in polynomial time.
So hamiltonian cycle problem is in class NP.


Step 2: Prove that hamiltonian cycle problem is NP-hard.
We know that a problem is NP-Hard, if every problem in NP can be reduced to this problem in polynomial time.
The approach we used is as follows:
In the previous section, we already proved that all NP problems can be reduced to SAT. Then, again we found that SAT problem can be reduced to 3-CNF-SAT problem. Again, we reduced 3-CNF-SAT problem to clique problem. again, we reduced clique problem to vertex cover problem. Then, if we can reduce vertex cover problem to hamiltonian cycle problem in polynomial time, we can say that hamiltonian cycle problem is NP-hard.
Hamiltonian Cycle Problem Computer Science Engineering (CSE) Notes | EduRev
We need to reduce vertex cover problem to hamiltonian cycle problem.

Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!

Related Searches

Important questions

,

practice quizzes

,

Summary

,

Exam

,

pdf

,

Sample Paper

,

Free

,

past year papers

,

Hamiltonian Cycle Problem Computer Science Engineering (CSE) Notes | EduRev

,

shortcuts and tricks

,

ppt

,

video lectures

,

Hamiltonian Cycle Problem Computer Science Engineering (CSE) Notes | EduRev

,

Objective type Questions

,

Viva Questions

,

Semester Notes

,

study material

,

MCQs

,

Hamiltonian Cycle Problem Computer Science Engineering (CSE) Notes | EduRev

,

Extra Questions

,

Previous Year Questions with Solutions

,

mock tests for examination

;