1
$\begingroup$

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.

Related to Permutation similarity of matrices with many distinct entries

For random regular graphs the algorithm is $O(\log_2(n)n^4)$.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ There are lots of test graphs here: pallini.di.uniroma1.it/Graphs.html $\endgroup$
    – Brendan McKay
    Commented Jun 24, 2023 at 14:41
  • $\begingroup$ @BrendanMcKay Many thanks for this useful resource. $\endgroup$
    – joro
    Commented Jun 26, 2023 at 17:58

0

Reset to default

You must log in to answer this question.