The graph isomorphism problem has a long history in the fields of computer science, mathematics and chemistry. Graph isomorphism is very important due to its practical applications and its unique complexity theoretic status . Informally, graph isomorphism is to check if two graphs that look different are actually the same. More formally, given two graphs does there exist a 1-to-1 mapping of vertices in one graph onto the vertices of other such that edges and non-edges are preserved?. Example of two isomorphic graphs is given below

A more interesting example is below

Some of the applications of Graph Isomorphism are verification of computer programs, Security, for example fingerprint scanners, facial scanners etc. The problem is in class NP (nondeterministic polynomial time) mean given a solution (bijective mapping) you can verify the solution efficiently.

## Comments

Sort by:

TopNewestCan the graph isomorphism problem be solved in polynomial time? – Agnishom Chattopadhyay · 4 months, 2 weeks ago

Log in to reply

– Shivdutt Sharma · 4 months, 2 weeks ago

till now no one is able to solve the problem in polynomial time in general (For some special class of graphs it is solvable in polynomial time like for trees)Log in to reply

– Calvin Lin Staff · 4 months ago

Note: Laszlo Babai showed last year that Graph Isomorphism is in Quasipolynomial-time.Log in to reply