Algorithm for Subgraph Isomorphism

Ullmann, J.R. An algorithm for subgraph isomorphism. /. Assoc. Comput. Machinery. 1976, 23, 31-42. 

Ullmann J R 1976. An Algorithm for Subgraph Isomorphism. Journal of the Association for Computing Machinery 23 31-42. 

Raymond JW, Willett P. Maximum common subgraph isomorphism algorithms for the matching of chemical structures. J Comput-Aided Mol Des 2002 16 521-33. 

The refinement procedure utilises the fact that if some query node Q(X) has another node Q(fV) at some specific distance ) ( and/or angle), and if some database node D(Z) matches with Q(W), then there must also be some node D(Y) at the appropriate distance(s) from D(Z) which matches with Q(X) this is a necessary, but not sufficient, condition for a subgraph isomorphism to be present (except in the limiting case of all the query nodes having been matched, when the condition is both necessary and sufficient). The refinement procedure is called before each possible assignment of a database node to a query node and the matched substructure is increased by one node if, and only if, the condition holds for all nodes W, X, Y and Z. The basic algorithm terminates once a match has been detected or until a mismatch has been confirmed [70] it is easy to extend the algorithm to enable the detection of all matches between a query pattern and a database structure, as is required for applications such as those discussed here. 

The presence or absence of isomorphism for a pair of graphs is determined by an isomorphism algorithm. Specifically, graph isomorphism, subgraph... 

Ideally, what is required is an algorithm which tests for the subgraph isomorphism in polynomial time (i.e., the time taken is a direct function of the number of nodes, or its square or cube etc.). Unfortunately, no such algorithm is known, and it is strongly suspected by mathematicians that no such algorithm exists, though this has not been proven. 

The subgraph isomorphism problem is one of a class of mathematical problems known as NP-complete (another is the well-known travelling salesman problem) and it has been proved that if a polynomial-time algorithm exists for one of these, such algorithms must exist for all of them. But none of them yet has a polynomial time algorithm. 

---