AVERAGE-CASE AND SMOOTHED ANALYSIS OF GRAPH ISOMORPHISM

• 成果类型: Article
• 署名作者: Gaudio, Julia; Racz, Milkos Z.; Sridhar, Anirudh
• 署名单位: Northwestern University; Northwestern University; Northwestern University; Massachusetts Institute of Technology (MIT)
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/25-AAP2146
• 发表日期: 2025
• 页码: 1373-1406
• 关键词: algorithms

摘要

We propose a simple and efficient local algorithm for graph isomorphism which succeeds for a large class of sparse graphs. This algorithm produces a low-depth canonical labeling, which is a labeling of the vertices of the graph that identifies its isomorphism class using vertices' local neighborhoods. Prior work by Czajka and Pandurangan showed that in the Erdos-R & eacute;nyi model G(n, pn), 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 npn = omega (log4(n)/ log log n) (and pn <= 1/2); subsequently, Mossel and Ross showed that the same holds when npn = omega(log2(n)). We first show that their analysis essentially cannot be improved: we prove that when npn = o(log2(n)/(log log n)3), with high probability there exist distinct vertices with isomorphic 2-neighborhoods. Our first main result is a positive counterpart to this, showing that 3-neighborhoods give a canonical labeling when npn >= (1 + delta) log n (and pn <= 1/2); this improves a recent result of Ding, Ma, Wu and Xu, completing the picture above the connectivity threshold. Our second main result is a smoothed analysis of graph isomorphism, showing that for a large class of deterministic graphs, a small random perturbation of the edge set yields a graph which admits a canonical labeling from 3-neighborhoods, with high probability. While the worst-case complexity of graph isomorphism is still unknown, this shows that graph isomorphism has polynomial smoothed complexity.