Canonization of a random graph by two matrix-vector multiplications

Abstract

We show that a canonical labeling of a random $n$-vertex graph can be obtained by assigning to each vertex $x$ the triple $(w_1(x),w_2(x),w_3(x))$, where $w_k(x)$ is the number of walks of length $k$ starting from $x$. This takes time $O(n^2)$, where $n^2$ is the input size, by using just two matrix-vector multiplications. The linear-time canonization of a random graph is the classical result of Babai, Erdős, and Selkow. For this purpose they use the well-known combinatorial color refinement procedure, and we make a comparative analysis of the two algorithmic approaches.

32 pages, 3 Figures. Introduction was extended (implications for distributed computation were added)