Heuristics and Really Hard Instances for Subgraph Isomorphism Problems / 631
Ciaran McCreesh, Patrick Prosser, James Trimble

We show how to generate "really hard'" random instances for subgraph isomorphism problems. For the non-induced variant, we predict and observe a phase transition between satisfiable and unsatisfiable instances, with a corresponding complexity peak seen in three different solvers. For the induced variant, much richer behaviour is observed, and constrainedness gives a better measure of difficulty than does proximity to a phase transition. We also discuss variable and value ordering heuristics, and their relationship to the expected number of solutions.

PDF