A Parallel, Backjumping Subgraph Isomorphism Algorithm using Supplemental Graphs

Contributing Authors: 
  • Ciaran McCreesh
  • Patrick Prosser

The subgraph isomorphism problem involves finding a pattern graph inside a target graph. We present a new bit- and thread-parallel constraint-based search algorithm for the problem, and experiment on a wide range of standard benchmark instances to demonstrate its effectiveness. We introduce supplemental graphs, to create implied constraints. We use a new low-overhead, lazy variation of conflict directed backjumping which interacts safely with parallel search, and a counting-based all-different propagator which is better suited for large domains.

Box Type: