Research work · 2016

Heuristics and really hard instances for subgraph isomorphism problems

Ciaran McCreesh, Patrick Prosser, James Trimble

ENLIGHTEN (Jurnal Bimbingan dan Konseling Islam)

Abstract

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 unsatis- fiable 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.