2024/10/08 by Anastos, Michael, Kwan, Matthew, Moore, Benjamin · 1 citation
#Combinatorics (math.CO) #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2410.06095
There is no known polynomial-time algorithm for graph isomorphism testing, but elementary combinatorial "refinement" algorithms seem to be very efficient in practice. Some philosophical justification is provided by a classical theorem of Babai, Erdős and Selkow: an extremely simple polynomial-time combinatorial algorithm (variously known as "naïve refinement", "naïve vertex classification", "colour refinement" or the "1-dimensional Weisfeiler-Leman algorithm") yields a so-called canonical labelling scheme for "almost all graphs". More precisely, for a typical outcome of a random graph G(n,1/2), this simple combinatorial algorithm assigns labels to vertices in a way that easily permits isomorphism-testing against any other graph. We improve the Babai-Erdős-Selkow theorem in two directions. First, we consider randomly perturbed graphs, in accordance with the smoothed analysis philosophy of Spielman and Teng: for any graph G, naïve refinement becomes effective after a tiny random perturbation to G (specifically, the addition and removal of O(nlog n) random edges). Actually, with a twist on naïve refinement, we show that O(n) random additions and removals suffice. These results significantly improve on previous work of Gaudio-Rácz-Sridhar, and are in certain senses best-possible. Second, we complete a long line of research on canonical labelling of random graphs: for any p (possibly depending on n), we prove that a random graph G(n,p) can typically be canonically labelled in polynomial time. This is most interesting in the extremely sparse regime where p has order of magnitude c/n; denser regimes were previously handled by Bollobás, Czajka-Pandurangan, and Linial-Mosheiff. Our proof also provides a description of the automorphism group of a typical outcome of G(n,pn) (slightly correcting a prediction of Linial-Mosheiff).