The probabilistic Weisfeiler-Leman algorithm

Abstract

A probabilistic version of the Weisfeiler-Leman algorithm for computing the coherent closure of a colored graph is suggested. The algorithm is Monte Carlo and runs in time $O(n^{1+\omega }{\log }^{2}n)$, where $n$ is the number of vertices of the graph and $\omega <2.273$ is the matrix multiplication exponent.

arXiv comment7 pages