Reducing Complexity of Graph Isomorphism Problem (International Journal of Innovative Research in Computer Science & Technology, 2020)
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.
Keywords: Graph isomorphism; canonical representation; equivalence class, polynomial