search

ciaranm / glasgow-subgraph-solver

A solver for subgraph isomorphism problems, based upon a series of papers by subsets of McCreesh, Prosser, and Trimble.
MIT License
70 stars 23 forks source link

Benchmark instances #5

Open bkj opened 3 years ago

bkj commented 3 years ago

Hi --

I see in your papers that you often discuss the importance of having good benchmark instance across a wide variety of graphs for benchmarking these kinds of algorithms.

I'm relatively new to the subgraph matching domain -- are there repositories of problem instances that you can point me to? Either one that you use for your own research, or the "canonical problem instances" used by the subgraph matching community more broadly. I poked around a bit online, but haven't found anything particularly obvious.

Thanks!

ciaranm commented 3 years ago

Yes, https://perso.liris.cnrs.fr/christine.solnon/SIP.html is a good place to start, although that collection includes the dodgy MIVIA instances (which are all satisfiable, and not very hard other than their size) as well as the tougher instances. If you're looking for the exact set of pattern / target pairs that I use, you can find it in this list:

https://github.com/ciaranm/cpaior2019-sbs-for-subgraphs-paper/blob/master/experiments/instances.txt

You'll also see references to AIDS, PDBS, PCM, and PPI in some papers: these instances are all trivially solvable by any half-way decent algorithm, so if a paper is finding any of those hard, it's a sign they're using a really bad algorithm.