Benchmarks for the Subgraph Isomorphism Problem
# 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).

### Graph format:

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.

### Experimental Evaluation:

An experimental comparison of different subgraph isomorphism solvers is described in:
**Experimental Evaluation of Subgraph Isomorphism Solvers**

Christine Solnon

Invited Talk at 12th IAPR International Workshop on Graph-based Representations in Pattern Recognition (GbR), LNCS, Springer

Paper (pdf)