Benchmark Graphs for Practical Graph Isomorphism

Understand

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.