Skip to main content
2 of 4
time for srg
joro
  • 25.4k
  • 10
  • 66
  • 121

Hard instances for this graph isomorphism algorithm based on powers of weighted adjacency matrices?

In short, I found an algorithm for GI and the only hard instances I found so far are non-isomorphic strongly regular graphs with large automorphism groups.

Q1 What are hard instances for the alogrithm?

The sage math code and the preprint

and the code in a browser on sagemath.org

Some success stories:

The Paley graph of order $73$ was solved in $9$ recursive calls (each polynomial) and time 703 ms.

The strongly regular graph with parameters $(100, 44, 18, 20)$ was solved in $12$ calls and time 1.5 sec.

joro
  • 25.4k
  • 10
  • 66
  • 121