ISO problem is to decide whether there is a bijective mapping from the nodes of one graph to the nodes of the second graph such that the edge connections are respected. It is considered to be a hard problem and is not known to be in P or NP-Complete. Many researchers believe that ISO is not NP-Complete !! A complexity class called GI (graph isomorphism), (which is conjectured to be disjoint from both P and NP-Complete) is defined to understand the complexity of ISO !!

However, NP-Completeness of sub-graph isomorphism can be proved by reduction from HAMILTONIAN-PATH. (duh !)

ISO is in P for the following restricted classes :

- bounded-degree graphs
- planar graphs
- trees (read this book "Algorithms on Trees and Graphs" by Gabriel Valiente for the various versions of tree-isomorphism (labeled vs unlabeled, top-down vs bottom-up))

ISO finds its applications in a wide range of areas like computational biology, data-mining, computational chemistry, matrix theory and so on. If you are looking for software, nauty serves as an excellent practical tool for graph isomorphism.

## No comments:

Post a Comment