Heuristics and Really Hard Instances for Subgraph Isomorphism Problems
Authors: Ciaran McCreesh, Patrick Prosser, James Trimble
IJCAI 2016 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Our experiments were performed on systems with Intel Xeon E5-4650 v2 CPUs, running Scientific Linux release 6.7. We selected three subgraph isomorphism solvers: the Glasgow solver [Mc Creesh and Prosser, 2015], LAD [Solnon, 2010], and VF2 [Cordella et al., 2004]; each was compiled using GCC 4.9. In each case we measure the number of recursive calls (guessed assignments) made, not runtimes. We are not aiming to compare absolute performance between solvers; rather, we are looking for solver-independent patterns of difficulty. We used a timeout of 1,000 seconds, which was enough for the Glasgow solver to solve nearly all our instances (whose orders were selected with this timeout in mind), although we may slightly overestimate the proportion of unsatisfiable instances for extremely sparse or dense pattern graphs. The LAD and VF2 solvers experienced many more failures with this timeout, so our picture of just how hard the hardest instances are with these solvers is less detailed. |
| Researcher Affiliation | Academia | University of Glasgow, Glasgow, Scotland |
| Pseudocode | No | The paper does not contain any pseudocode or clearly labeled algorithm blocks. |
| Open Source Code | No | The paper does not provide any explicit statements or links indicating that the source code for their methodology (e.g., the instance generation method) is open-source or publicly available. |
| Open Datasets | Yes | The random instances used in each case came from common datasets [De Santo et al., 2003; Zampelli et al., 2010], which were generated by taking a random subgraph of a random (Erd os-R enyi, scale-free, bounded degree, or mesh) graph and permuting the vertices. |
| Dataset Splits | No | The paper describes generating random instances and testing solvers on them based on certain parameters. It does not specify typical train/validation/test splits as used in machine learning for model training and evaluation. |
| Hardware Specification | Yes | Our experiments were performed on systems with Intel Xeon E5-4650 v2 CPUs, running Scientific Linux release 6.7. |
| Software Dependencies | Yes | We selected three subgraph isomorphism solvers: the Glasgow solver [Mc Creesh and Prosser, 2015], LAD [Solnon, 2010], and VF2 [Cordella et al., 2004]; each was compiled using GCC 4.9. We used the Clasp solver [Gebser et al., 2011] version 3.1.3 to solve the pseudo-boolean instances. |
| Experiment Setup | Yes | Suppose we arbitrarily decide upon a pattern graph order of 20, a target graph order of 150, and a fixed target edge probability of 0.40. As we vary the pattern edge probability from 0 to 1, we would expect to see a shift from entirely satisfiable instances to entirely unsatisfiable instances... We used a timeout of 1,000 seconds... |