Open Collections

Description

The subgraph isomorphism problem (SIP) asks, given a smaller (pattern) graph P can we find it inside a larger (target) graph T? The combinatorial search techniques used to answer this question follow the approaches used in SAT and CP, and thus should benefit from symmetry breaking. I will introduce methods for dynamic symmetry breaking for SIP, which can be applied to pattern graphs (variables) or target graphs (values) (and some combinations thereof) which are rooted in group theory and thus are generic enough to be applicable to (almost) any combinatorial search problem. I will talk through the correctness challenges we have encountered in the development of the techniques, as well as the challenges that we are facing when going from a decision to an enumeration problem.