A Parallel Algorithm for Subgraph Isomorphism (Brief Announcement)

Subgraph isomorphism is a fundamental property of graphs that requires checking whether the network structure of one graph can be found (embedded) within another graph. It has numerous applications and is a computationally challenging problem: it is NP-complete and known algorithms explore an exponentially large search space. Even though it has been studied extensively, relatively little is known about whether subgraph isomorphism accepts a theoretically and practically efficient parallel solution. In this paper, we present our ongoing work on designing a parallel algorithm for the subgraph (and graph) isomorphism problem, which addresses challenges commonly faced when attempting to obtain a parallel algorithm for isomorphism. Our algorithm appears to scale well up to the 70 cores of our empirical machine.