I have found a algorithm to check whether a Hamiltonian Cycle Exists in the graph or not, but not able to compute/analyse it's time complexity.
The algorithm is as follows :
- Label all the vertices with distinct prime numbers.
- Label all edges with weight equal to 1.
- Now remove one vertex at a time, while removing a vertex v, if there is edge between u and v & v and w, then add a edge between u and w, with weight = weight(u->v)*weight(v->w)*label(v)
- If at the end you end up with only one vertex with self edges and if there is a self edge that is equal to the product of all the primes of the removed vertices then there is Hamiltonian Cycle.
I have proved the algorithm is correct but unable to find it's time complexity. I think there can be much more optimization in this algorithm also, as we don't need to add those edges to the graph that whose weight divides the weight of some other already present edge. If someone can give some optimization to this algorithm it may turn out to be polynomial, thus proving P = NP.