What is a Graph Isomorphism?
Graphs G and H are said to be isomorphic if there exists a mapping, hk = m(gi), that preserves the adjacency of all nodes [foulds92]. Any application-specific node and edge colorings must also be consistent under the mapping. Subgraph isomorphism is a condition of isomorphism that exists between two subgraphs of G and H. The goal for a subgraph-matching algorithm is to have a maximal number of nodes in each subgraph. Why is Determining Graph Isomorphism Difficult? The amount of effort associated with an exact solution would typically be considered intractable, requiring an amount of effort that is exponential in the number of nodes, N. Note there are N! possible orderings of nodes. The subgraph isomorphism problem is even worse combinatorically, as the size of the matching subgraph is unknown. The subgraph isomorphism is proven to be NP-Complete. However, the class of difficulty for the graph isomorphism problem is unknown [West01]. It is due to the NP-Completeness of the subgraph isom
