ML Anthology

Heuristics and Really Hard Instances for Subgraph Isomorphism Problems

Ciaran McCreesh, Patrick Prosser, James Trimble
IJCAI 2016 pp. 631-638
/ijcai/2016/mccreesh2016ijcai-heuristics/

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

PDF IJCAI Semantic Scholar

Cite

Text

McCreesh et al. "Heuristics and Really Hard Instances for Subgraph Isomorphism Problems." International Joint Conference on Artificial Intelligence, 2016.

Markdown

[McCreesh et al. "Heuristics and Really Hard Instances for Subgraph Isomorphism Problems." International Joint Conference on Artificial Intelligence, 2016.](https://mlanthology.org/ijcai/2016/mccreesh2016ijcai-heuristics/)

BibTeX

@inproceedings{mccreesh2016ijcai-heuristics,
  title     = {{Heuristics and Really Hard Instances for Subgraph Isomorphism Problems}},
  author    = {McCreesh, Ciaran and Prosser, Patrick and Trimble, James},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year      = {2016},
  pages     = {631-638},
  url       = {https://mlanthology.org/ijcai/2016/mccreesh2016ijcai-heuristics/}
}