Benchmark Graphs for Practical Graph Isomorphism
From MaRDI portal
Publication:5111749
Abstract: The state-of-the-art solvers for the graph isomorphism problem can readily solve generic instances with tens of thousands of vertices. Indeed, experiments show that on inputs without particular combinatorial structure the algorithms scale almost linearly. In fact, it is non-trivial to create challenging instances for such solvers and the number of difficult benchmark graphs available is quite limited. We describe a construction to efficiently generate small instances for the graph isomorphism problem that are difficult or even infeasible for said solvers. Up to this point the only other available instances posing challenges for isomorphism solvers were certain incidence structures of combinatorial objects (such as projective planes, Hadamard matrices, Latin squares, etc.). Experiments show that starting from 1500 vertices our new instances are several orders of magnitude more difficult on comparable input sizes. More importantly, our method is generic and efficient in the sense that one can quickly create many isomorphism instances on a desired number of vertices. In contrast to this, said combinatorial objects are rare and difficult to generate and with the new construction it is possible to generate an abundance of instances of arbitrary size. Our construction hinges on the multipedes of Gurevich and Shelah and the Cai-F"{u}rer-Immerman gadgets that realize a certain abelian automorphism group and have repeatedly played a role in the context of graph isomorphism. Exploring limits of such constructions, we also explain that there are group theoretic obstructions to generalizing the construction with non-abelian gadgets.
Recommendations
- A large database of graphs and its use for benchmarking graph isomorphism algorithms
- Efficient Method to Perform Isomorphism Testing of Labeled Graphs
- Publication:4206773
- Practical graph isomorphism. II.
- Graph similarity and approximate isomorphism
- On tractable parameterizations of graph isomorphism
- scientific article; zbMATH DE number 1839469
- Approximate graph isomorphism
- A general comparative study of some aspects of graph isomorphism
- Efficient Suboptimal Graph Isomorphism
Cites work
- scientific article; zbMATH DE number 3664988 (Why is no real title available?)
- scientific article; zbMATH DE number 1004939 (Why is no real title available?)
- An exponential lower bound for individualization-refinement algorithms for graph isomorphism
- An optimal lower bound on the number of variables for graph identification
- Benchmark Graphs for Practical Graph Isomorphism
- Choiceless polynomial time on structures with small abelian colour classes
- Conflict propagation and component recursion for canonical labeling
- Graph isomorphism in quasipolynomial time (extended abstract)
- Isomorphism of graphs of bounded valence can be tested in polynomial time
- On finite rigid structures
- On the Hardness of Graph Isomorphism
- Polynomial-time isomorphism test for groups with abelian Sylow towers.
- Practical graph isomorphism. II.
- Random Graph Isomorphism
- Reduction Techniques for Graph Isomorphism in the Context of Width Parameters
- Subgroups of 3-factor direct products
- The Power of Counting Logics on Restricted Classes of Finite Structures
Cited in
(13)- Leveraging special-purpose hardware for local search heuristics
- Graph similarity and approximate isomorphism
- Isomorphism test for digraphs with weighted edges
- Attacks on hard instances of graph isomorphism
- scientific article; zbMATH DE number 7445162 (Why is no real title available?)
- Practical graph isomorphism. II.
- A large database of graphs and its use for benchmarking graph isomorphism algorithms
- Identifiability of graphs with small color classes by the Weisfeiler-Leman algorithm
- Benchmark Graphs for Practical Graph Isomorphism
- An exponential lower bound for individualization-refinement algorithms for graph isomorphism
- Constructing hard examples for graph isomorphism
- ScrewBox: a randomized certifying graph-non-isomorphism algorithm
- Robust worst cases for parity games algorithms
This page was built for publication: Benchmark Graphs for Practical Graph Isomorphism
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111749)
