A Randomized Certifying Graph-Non-Isomorphism Algorithm

Our algorithm aims at solving difficult instances by producing randomized certificates for non-isomorphism.

Non-isomorphism can be detected very quickly this way, however
it is inherent to our approach that it performs better
on pairs of non-isomorphic graphs than on isomorphic instances.

The algorithm randomly samples substructures in two given graphs in
order to detect dissimilarities between them. The choice of the
sought-after structures as well as the tuning of the search process
is dynamically adapted during the sampling. Eventually, a
randomized certificate is produced by which the user can verify the
non-isomorphism of the input graphs.

I will outline a simple version of the algorithm, the statistically
testable certification predicates as well as structural properties of
graphs that appear to be difficult.