2025-11-25T10:28:17.626083

Smoothed analysis for graph isomorphism

Anastos, Kwan, Moore

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).

academic

グラフ同型性に対する平滑化分析

基本情報

論文ID: 2410.06095
タイトル: Smoothed analysis for graph isomorphism
著者: Michael Anastos, Matthew Kwan, Benjamin Moore
分類: math.CO cs.CC cs.DS
発表時期: 2024年10月
論文リンク: https://arxiv.org/abs/2410.06095v3

要約

グラフ同型性判定問題には既知の多項式時間アルゴリズムが存在しないが、基本的な組合せ的「細分化」アルゴリズムは実践において非常に効率的である。Babai、Erdős、Selkowの古典的定理はこれに対する哲学的説明を提供する：極めてシンプルな多項式時間組合せアルゴリズム（「素朴な細分化」、「素朴な頂点分類」、「色細分化」または「1次元Weisfeiler-Leman アルゴリズム」と呼ばれる）は「ほぼすべてのグラフ」に対して正規ラベリング方式を提供できる。

本論文はBabai-Erdős-Selkow定理を2つの方向で改善する：第一に、Spielmanとtengの平滑化分析の考え方に基づいてランダムに摂動されたグラフを考察する；第二に、ランダムグラフの正規ラベリングに関する長期的な研究課題を完成させる。