The subgraph isomorphism problem is a well known problem for algorithm engineers. It is , given a graph G and a graph g, to verify whether "G has a subgraph which is isomorphic to g" or not. It is an NP-complete problem.
But for some special cases (if G is a tree or planar), it had been shown that, subgraph isomorphism problem can be solved in polynomial time. But in real world applications graphs may not be trees(or planar) always.So the current research interest is to develop some heuristic algorithms for such NP-complete problems, which have high probability of success.
So , the goal of this project is to come up with some heuristic approximation(polynomial) algorithm for the problem of subgraph isomorphism, which runs with high probabilty of success.
Materials
An introduction to subgraph isomorphism and related problems(slides) pdf