Two parallel versions of VF3: Performance analysis on a wide database of graphs

An important combinatorial problem is subgraph isomorphism, which formalizes the task of searching for occurrences of a known substructure within a larger structure represented by a graph: applications are in the fields of chemistry, biology, medicine, databases, social network analysis. Subgraph isomorphism has been proven to be NP-complete in the general case, but several algorithms exist that use heuristics to achieve an affordable run time for common classes of graphs. The need of working with larger and larger graphs makes attractive the idea of parallelizing this task; however, a consensus has not yet been reached on what is the best strategy for doing so. In this paper, we present two versions of a new, parallel algorithm that is based on a re-design of the well known VF3 algorithm. We discuss the changes that were made to efficiently distribute the work among multiple processors. The algorithms have been evaluated with a comprehensive experimentation, using several publicly available graph datasets, to demonstrate their effectiveness in exploiting the parallelism.