Smoothed analysis for graph isomorphism Anastos, Michael Kwan, Matthew Alan ; https://orcid.org/0000-0002-4003-7567 Moore, Benjamin ddc:000 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. Association for Computing Machinery 2025 info:eu-repo/semantics/conferenceObject doc-type:conferenceObject text http://purl.org/coar/resource_type/c_5794 https://research-explorer.ista.ac.at/record/20007 https://research-explorer.ista.ac.at/download/20007/20012 Anastos M, Kwan MA, Moore B. Smoothed analysis for graph isomorphism. In: <i>Proceedings of the 57th Annual ACM Symposium on Theory of Computing</i>. Association for Computing Machinery; 2025:2098-2106. doi:<a href="https://doi.org/10.1145/3717823.3718173">10.1145/3717823.3718173</a> eng info:eu-repo/semantics/altIdentifier/doi/10.1145/3717823.3718173 info:eu-repo/semantics/altIdentifier/issn/0737-8017 info:eu-repo/semantics/altIdentifier/isbn/9798400715105 info:eu-repo/semantics/altIdentifier/arxiv/2410.06095 info:eu-repo/semantics/openAccess