Symmetry breaking in the subgraph isomorphism problem

The Subgraph Isomorphism Problem (SIP) asks whether a given graph occurs within another. Despite being theoretically difficult, SIP can be solved quickly in practice. Symmetry breaking identifies symmetric states during the search process, and avoids searching all of them. Symmetry breaking has been shown to be useful in reducing runtimes for constraint programming, but there are many varied approaches with nuanced differences. It is unclear which symmetry breaking technique is "best" for SIP. We present various symmetry breaking techniques with a focus on influencing constraints to reflect the search order, and study the efficacy of each. Initial experimental data indicates significant speed-up over the solver with no symmetry breaking, and proposed improvements to basic techniques yield strong practical gains.