Complexity of Graph Isomorphism

With the weekend temperatures of CA reaching 100, I had no choice but to sit at home in front of my small but efficient table fan. Having nothing else to do, I picked up this book, 'The Graph Isomorphism Problem: Its Structural Complexity', addressing the complexity of the graph isomorphism problem (ISO). The book uses ISO to illustrate the concepts of structural complexity. I learnt more about the structural complexity theory from this book than the ISO itself. This book makes an excellent weekend read (if you have some necessary background in graph theory and computational complexity). I am glad I read this book.

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.