Graph matching problems of varying types are important in a wide array of application areas. A graph matching problem is a problem involving some form of comparison between graphs. Some of the many application areas of such problems include information retrieval, sub-circuit identification, chemical structure classification, and networks. Problems of efficient graph matching arise in any field that may be modeled with graphs. For example, any problem that can be modeled with binary relations between entities in the domain is such a problem. The individual entities in the problem domain become nodes in the graph. And each binary relation becomes an edge between the appropriate nodes. Although it is possible to formulate such a large array of problems as graph matching problems, it is not necessarily a good idea to do so.

Graph matching is a very difficult problem. The graph isomorphism problem is to determine if there exists a one-to-one mapping from the nodes of one graph to the nodes of a second graph that preserves adjacency. Similarly, the subgraph isomorphism problem is to determine if there exists a one-to-one mapping from the nodes of a given graph to the nodes of a subgraph of a second graph that preserves adjacency. The largest common subgraph problem is to find the largest subgraphs of two given graphs such that the subgraphs are isomorphic. The digraph D-morphism problem is to determine if there exists a one-to-one mapping from the nodes of one directed graph to the nodes of a second directed graph that preserves adjacency if you disregard the directions of the arcs. The closely related problems of subgraph isomorphism, largest common subgraph, and digraph D-morphism are known to be NP-complete. Whether or not the graph isomorphism problem is in the class of NP-complete problems is an open question. Although there do exist special cases of each of these problems that can be solved in polynomial time, there do not exist known algorithms of polynomial complexity to solve these problems in the general case. Therefore, the search for more efficient solutions to these problems is of great importance.