Smoothed Analysis for Graph Isomorphism

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 for this phenomenon 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.

Authors

• Michael Anastos
• Matthew Kwan 0001
• Benjamin R. Moore

Keywords

• Colour Refinement
• Graph Isomorphism
• Smoothed Analysis
• Weisfeiler-Leman Algorithm