论文标题
图同构的平均案例和平滑分析
Average-case and smoothed analysis of graph isomorphism
论文作者
论文摘要
我们为图同构提出了一种简单有效的局部算法，该算法为大量的稀疏图而成功。该算法产生低深度的规范标签，该标记是图形顶点的标记，使用顶点的本地邻域识别其同构类别。 Czajka和Pandurangan的先前工作表明，顶点的度曲线（即，其邻居度的排序列表）在$ N P_N =ω（\ log log^{4}（4}（4}（n） / \ log log n） / \ log n）$（和$ p_（和$ p_} n} n} n} n}时随后，Mossel和Ross表明，当$ n p_n =ω（\ log^{2}（n））$时，相同的成绩也相同。我们首先表明他们的分析基本上不能改进：我们证明，当$ n p_n = o（\ log^{2}（n） /（\ log \ log \ log \ log \ log \ log n）^{3}）$，具有很高的可能性，存在具有异态$ 2 $ neighighborhoods的不同可能性。我们的第一个主要结果是与此相对应的正面结果，表明$ 3 $ neighborhoods会在$ n p_n \ geq（1+δ）\ log n $（和$ p_n \ p_n \ leq 1/2 $）时给出规范的标签；这改善了Ding，Ma，Wu和Xu的最新结果，完成了连接阈值上方的图片。 我们的第二个主要结果是对图的同构平滑分析，表明对于大量的确定性图，一个小的随机扰动可确保$ 3 $ neighborhoods具有很高可能性的规范标记。尽管图同构的最坏情况仍然未知，但这表明图同构具有多项式平滑的复杂性。
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 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 = ω( \log^{4}(n) / \log \log n )$ (and $p_{n} \leq 1/2$); subsequently, Mossel and Ross showed that the same holds when $n p_n = ω( \log^{2}(n) )$. We first show that their analysis essentially cannot be improved: we prove that when $n p_n = o( \log^{2}(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 $n p_n \geq (1+δ) \log n$ (and $p_n \leq 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 ensures that $3$-neighborhoods give a canonical labeling with high probability. While the worst-case complexity of graph isomorphism is still unknown, this shows that graph isomorphism has polynomial smoothed complexity.
