Average-case and smoothed analysis of graph isomorphism

arXiv2211.16454MaRDI QIDQ6418951FDOQ6418951

Authors: Julia Gaudio, Miklós Z. Rácz, Anirudh Sridhar 

Publication date: 29 November 2022

Abstract: We study local canonical labeling algorithms on an ErdH{o}s--R'enyi random graph $G(n,p_n)$. A canonical labeling algorithm assigns a unique label to each vertex of an unlabeled graph such that the labels are invariant under isomorphism. Here we focus on local algorithms, where the label of each vertex depends only on its low-depth neighborhood. Czajka and Pandurangan showed that the degree profile of a vertex (i.e., the sorted list of the degrees of its neighbors) gives a canonical labeling with high probability when $n{p}_n=omega(lo{g}^4(n)/loglogn)$ (and $p_{n}leq1/2$); subsequently, Mossel and Ross showed that the same holds when $n{p}_n=omega(lo{g}^2(n))$. Our first result shows that their analysis essentially cannot be improved: we prove that when $n{p}_n=o(lo{g}^2(n)/(loglogn{)}^3)$, with high probability there exist distinct vertices with isomorphic $2$-neighborhoods. Our main result is a positive counterpart to this, showing that $3$-neighborhoods give a canonical labeling when $n{p}_{n}geq(1+delta)logn$ (and $p_{n}leq1/2$); this improves a recent result of Ding, Ma, Wu, and Xu, completing the picture above the connectivity threshold. We also discuss implications for random graph isomorphism and shotgun assembly of random graphs.

This page was built for publication: Average-case and smoothed analysis of graph isomorphism

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6418951)