Optimized Backtracking for Subgraph Isomorphism

Subgraph isomorphism is a fundamental graph problem with many important applications. Given twographs G and SG, the subgraph isomorphism problem is to determine whether G contains a subgraph thatis isomorphic to SG. It is well known that the problem is NP complete in the worst case. In this paper, wepresent two new algorithms for subgraph isomorphism problem for labeled graphs. If the graphs haveunique vertex labels, we designed a new algorithm based on modified adjacency list that has achievedlinear performance. For general graphs we present another algorithm using optimized backtrackingsearch. Though this algorithm doesn’t guarantee polynomial time, it reduces the search space by applyingseveral pruning techniques. Simulation results show that our new algorithms are competitive with classicUllman’s algorithm and more recent VF2.