Benchmarks for the Subgraph Isomorphism Problem
Composition of the archive:
- Benchmarks described in [ZDS2010] and [Sol2010]:
- scalefree (100 instances): Each instance is composed of a target graph (between 200 and 1000 nodes) and a pattern graph (90% of the nodes of the target graph). All graphs are scale-free networks that have been randomly generated using a power law distribution of degrees.
- LV (112 graphs coming from Valiente): These graphs have different properties (connected, biconnected, triconnected, bipartite, planar, ...) and have between 10 and 6671 nodes.
- si (1170 instances coming from the Graph Database): Each instance is composed of a target graph (between 200 and 1296 nodes) and a pattern graph (between 20% and 60% of the nodes of the target graph). There are bounded valence graphs and modified bounded valence graphs, 4D meshes, and randomly generated graphs.
- Benchmarks described in [DSHJS2011]:
- images-CVIU11 (44 pattern graphs and 146 target graphs): Pattern graphs have between 22 and 151 nodes and target graphs have between 1072 and 5972 nodes. All graphs have been generated from segmented images.
- meshes-CVIU11 (6 pattern graphs and 503 target graphs): Pattern graphs have between 40 and 199 nodes and target graphs have between 208 and 5873 nodes. All graphs have been generated from meshes modelling 3D objects.
- Benchmark described in [SDHJ2015]:
- images-PR15 (1 target graph and 24 pattern graphs): The target graph has 4838 nodes and the pattern graphs have between 4 and 170 nodes. All graphs have been generated from segmented images.
- Benchmark described in [GFMSS2014]:
- biochemical reactions (136 graphs): All graphs are directed bipartite graphs which have between 9 and 386 nodes and which describe biocheminal reaction networks coming from biomodels.net.
- Benchmark generated by Ciaran McCreesh and Patrick Prosser (200 instances): Random graph instances chosen to be close to the satisfiable-unsatisfiable phase transition---these instances are expected to be particularly challenging, despite their small size (pattern graphs have 30 vertices; target graphs have 150 vertices).
Each graph is described in a text file.
If the graph has n vertices, then the file has n+1 lines:
- The first line gives the number n of vertices.
- The next n lines give, for each vertex, its number of successor nodes, followed by the list of its successor nodes.
An experimental comparison of different subgraph isomorphism solvers is described in:
- Experimental Evaluation of Subgraph Isomorphism Solvers
Invited Talk at 12th IAPR International Workshop on Graph-based Representations in Pattern Recognition (GbR), LNCS, Springer