Efficient Algorithm to Determine whether a given Graph is Hamiltonian or Not with All Possible Paths
Given a Graph G (V, E), We Consider the problem of deciding whether G is Hamiltonian, that is- whether or Not there is a simple cycle in E spanning all vertices in V. [1] However to Verify that the given cycle is Hamiltonian by checking whether it is permutation of the vertices of V and whether each of the consecutives edges along the cycle actually exists in the Graph. This Verification Algorithm can certainly be implemented to run in O (n2) time, where n is the length of the encoding of G [2]. But to predict in Advance that the Graph has Hamiltonian Cycle or not was still Exponential before this Algorithm. This Problem is known to be NPComplete hence cannot be solved in Polynomial time in |V| unless P=NP. However till today there was no known Criterion we can apply to determine the existence Hamiltonian Circuit in General [3]. For its Exponential time We can Refer to theorems: – Vertex Cover problem is polynomially transformable to the Hamiltonian circuit Problem for Directed graphs, hence the Hamiltonian Circuit problem for Directed Graph is NP-Complete and the Hamiltonian Circuit Problem for Directed Graph is Polynomialy transformable to Hamiltonian Cycle Problem for Undirected Graph, hence the Hamiltonian Cycle Problem for undirected Graph is NP-complete [4]. Note that these derivations are based on the CNF- Satisfiability. Through this Paper we have introduced a Newer Algorithm with different approach to determine whether a given Graph is Hamiltonian or Not with all possible Paths, by applying Few Mathematical and logical Operations. This provides necessary and sufficient condition for a graph to be Hamiltonian.
