Item

Abstract

We present a novel randomized approach to the graph isomorphism problem. Our
algorithm aims at solving difficult instances by producing randomized
certificates for \emph{non}-isomorphism. We compare our implementation to the
de facto standard nauty. On many of the hardest known instances, the incidence
graphs of finite projective planes, our program is considerably faster than
nauty.
However, it is inherent to our approach that it performs better on pairs of
non-isomorphic graphs than on isomorphic instances.

Our algorithm randomly samples substructures in the 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. As a byproduct of our
approach, we introduce a new concept of regularity for graphs which is meant to
capture the computational hardness of isomorphism problems on graphs.