---
title: "Heuristics and Really Hard Instances for Subgraph Isomorphism Problems"
authors:
  - "Ciaran McCreesh"
  - "Patrick Prosser"
  - "James Trimble"
doi: ""
url: "https://ijcai.org/proceedings/2016/96"
pdf: "https://ijcai.org/proceedings/2016/0096.pdf"
venue: "Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence"
year: 2016
pages: "631-637"
track: ""
keywords:
---

# Heuristics and Really Hard Instances for Subgraph Isomorphism Problems

Ciaran McCreesh, Patrick Prosser, James Trimble

*Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence*, pages 631-637.

## 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 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.