Local Heuristics for the Subgraph Isomorphism Problem

After decades of research, efficient subgraph isomorphism remains a central challenge in graph theory, with important implications for fields such as computer vision, bioinformatics, and social networks. While older solvers relied upon low-overhead search with local filtering, state-of-the-art approaches trade a higher memory and time overhead for a more sophisticated global filtering. This tradeoff allows newer solutions to solve many of the hardest benchmark instances within a set timeout limit, but we conjecture that for some applications a faster solver with a higher timeout rate may be a better choice. We introduce a solver which significantly improves upon the older low-overhead approach through the inclusion of rich local information from the input graphs. When compared against state-of-the-art solutions, we observe that our solver is still less effective on the hardest benchmarks, but significantly outperforms on easier cases.