Heuristics and Really Hard Instances for Subgraph Isomorphism Problems
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.
@inproceedings{ijcai2016p96,
title = {Heuristics and Really Hard Instances for Subgraph Isomorphism Problems},
author = {McCreesh, Ciaran and Prosser, Patrick and Trimble, James},
booktitle = {Proceedings of the Twenty-Fifth International Joint Conference on
Artificial Intelligence, {IJCAI-16}},
publisher = {AAAI Press / International Joint Conferences on Artificial Intelligence},
editor = {Subbarao Kambhampati},
pages = {631--637},
year = {2016},
month = {7},
url = {https://ijcai.org/proceedings/2016/96},
}
TY - CPAPER TI - Heuristics and Really Hard Instances for Subgraph Isomorphism Problems AU - McCreesh, Ciaran AU - Prosser, Patrick AU - Trimble, James T2 - Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-16 PB - AAAI Press / International Joint Conferences on Artificial Intelligence PY - 2016 SP - 631 EP - 637 UR - https://ijcai.org/proceedings/2016/96 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
