Benchmark Graphs for Practical Graph Isomorphism

 

Pascal Schweizer, Daniel Neuen

The state-of-the-art solvers for the graph isomorphism problem (e.g. bliss , nauty/traces , conauto , saucy , etc.) 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.
One of the most important constructions in this context is the Cai-Fürer-Immerman construction but from a practical standpoint these graphs can be solved in reasonable time. Other difficult examples available up to this point are incidence structures of combinatorial objects (such as projective planes, Hadamard matrices, Latin squares, etc.). While some of these graphs pose difficulty for practical algorithms there is no generic way to construct them and the number of available examples is quite limited.

  Urheberrecht: © Lehrstuhl Informatik 7  

To close this gap we introduce new constructions that employ CFI gadgets. Our base construction hinges on the multipedes of Gurevich and Shelah (see the corresponding paper). Their construction aims to describe a class of rigid structures that can not be canonized by the Weisfeiler-Leman algorithm. It is closely related to the CFI construction but yields rigid graphs (graphs without non-trivial automorphisms) eliminating the possibility of practical algorithms to collapse their search space based on automorphisms of the input graphs.
Since we are interested in benchmark graphs for practical solvers, it is imperative to keep all gadget constructions as small as possible. Therefore, we also present two techniques to reduce the number of vertices in the base construction while preserving its essential structure. A detailed description of these constructions as well as some generalizations and limitations can be found in the following paper.

Daniel Neuen and Pascal Schweitzer, Benchmark Graphs for Practical Graph Isomorphism, 2017, arXiv:1705.03686

Below you find several benchmark sets of graphs created with said constructions together with a short description of the set (e.g. which construction was used together with some parameter settings). All graphs are encoded in dimacs format. The graphs come in pairs, which are recognizable by the last index in the file name. This allows a performance analysis of solvers for which only an isomorphism test is available and no canonization option. For the "cfi-rigid-r2" and "cfi-rigid-t2" series these pairs are isomorphic. For the other families the graphs come (with high probability) in pairs of non-isomorphic graphs.

• The multipedes (on cyclic group Z₂)
  "cfi-rigid-z2" series
• The rigid base construction R(B^*(G_n,σ)) (on cyclic group Z₂)
  "cfi-rigid-r2" series
• The rigid base construction R^*(B(G_n,σ)) (on cyclic group Z₂)
  "cfi-rigid-s2" series
• The shrunken multipedes (on cyclic group Z₂)
  "cfi-rigid-t2" series
• The rigid base construction R(B(G_n,σ)) (on cyclic group Z₃)
  "cfi-rigid-z3" series
• The dihedral construction R(B(G_n,σ)) (on dihedral group D₃)
  "cfi-rigid-d3" series

Further benchmark graphs for the general performance evaluation of isomorphism solvers can for example also be found here and here.

Funding: Excellence Initiative of the German federal and state governments.