Parallel Search, Backjumping, and Brittle Skeletons

Mr Ciaran McCreesh, University of Glasgow

The subgraph isomorphism problem is to find a little pattern graph inside a big target graph. Most algorithms for the problem are based upon inference and backtracking search. I'll look at one of these algorithms, and discuss how to parallelise it. The main complication is backjumping: when a conflict is reached, this algorithm can sometimes prove that it is safe to backtrack several steps immediately. I'll discuss how we can refactor backjumping as a special kind of fold, and then explain why the standard fold skeleton is no good: to avoid getting an absolute slowdown, we need both controlled work-stealing, and work cancellation, neither of which have been given the attention they deserve in the literature.