Yunyoung Choi  Kunsoo Park

10.5626/JOK.2021.48.9.973

subgraph isomorphism bipartite matching backtracking search pruning technique

In recent years, it has become increasingly important to efficiently solve NP-hard graph problems. One of the fundamental problems in graph analysis is subgraph isomorphism. Given a query graph and a data graph, the subgraph isomorphism problem is to determine whether there is an embedding of the query graph in the data graph. Although a lot of practical algorithms have been developed for the problem, existing algorithms showed limited running time scalability in dealing with many real-world graphs. In this paper, we propose a new pruning technique based on bipartite matching which enables us to capture and remove redundancies in the search space. We also conduct experiments on several real datasets to show effectiveness of our technique.