Reducing Complexity of Graph Isomorphism Problem

Graph isomorphism has been discussed in the literature as NP-hard problem. It has applications in various areas. Work done earlier in this area employs backtracking for identifying isomorphism between given two graphs as a result with the increase in size of the graph the time to solve the problem becomes exponential. The proposed work presents a polynomial time algorithm (PTGI) which tries to solve graph isomorphism between given two directed graphs. Some distinguishing features associated with each vertex are stored. These features are exploited in dividing the vertices of the graph into equivalence classes from which canonical representation of the graph is generated. Comparing these features of the vertices of the given two graphs solves isomorphism in polynomial time.