Smoothed analysis for graph isomorphism
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866911212552323072 |
|---|---|
| author | Anastos, Michael Kwan, Matthew Moore, Benjamin |
| author_facet | Anastos, Michael Kwan, Matthew Moore, Benjamin |
| contents | 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(n\log 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,p_n)$ (slightly correcting a prediction of Linial-Mosheiff). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_06095 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Smoothed analysis for graph isomorphism Anastos, Michael Kwan, Matthew Moore, Benjamin Combinatorics Computational Complexity Data Structures and Algorithms 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(n\log 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,p_n)$ (slightly correcting a prediction of Linial-Mosheiff). |
| title | Smoothed analysis for graph isomorphism |
| topic | Combinatorics Computational Complexity Data Structures and Algorithms |
| url | https://arxiv.org/abs/2410.06095 |