未解決問題、応用数学と計算数学, 組合せ論と離散数学、1971年に提起

グラフ同型問題の計算量

未解決

$n = |V_1| = |V_2|$ 個の頂点を持つ2つの有限単純グラフ $G_1 = (V_1, E_1)$ と $G_2 = (V_2, E_2)$ が与えられたとき、グラフ同型問題（ $\mathrm{GI}$ ）は、 $\{u, v\} \in E_1$ と $\{\varphi(u), \varphi(v)\} \in E_2$ が同値となる全単射 $\varphi : V_1 \to V_2$ が存在するかを問う。 $\mathrm{GI}$ は計算量クラス $\mathsf{P}$ （決定性多項式時間 $n^{O(1)}$ ）に属するか。

提起者, 1971スティーブン・クック

研究の最前線 2026年時点

2026年時点で、グラフ同型問題が $\mathsf{P}$ に属するかどうかは未解決である。ラースロー・ババイの2015–2017年の準多項式時間アルゴリズムにより上界 $\exp((\log n)^{O(1)})$ が確立されており、ハラルド・ヘルフゴットは $(\log n)^c$ の指数として $c = 3$ が取れることを示した。ババイの突破口に続き、ポリ対数次元ワイスファイラー・レマン法（ $(\log n)^{O(1)}$ - $\mathrm{WL}$ ）や動的計画法による拡張が発展しているが、固定次元の $k$ - $\mathrm{WL}$ 判定法だけではすべてのグラフの $\mathrm{GI}$ を解けないことが蔡進一（Jin-Yi Cai）、フューラー、インマーマン（1992年）によって証明されている。

既知の最良の結果

ババイ（2015–2017年）：グラフ同型問題、文字列同型問題、および剰余類共通部分問題は決定性準多項式時間 $\exp((\log n)^{O(1)})$ で解ける。
ルクス（1982年）およびグローエ・ノイエン・シュヴァイツァー（2018年）：最大次数 $d$ のグラフに対し、同型判定は時間 $n^{\operatorname{poly}(\log d)}$ で可能である。
シェーニング（1988年）： $\mathrm{GI}$ は低階層 $\mathsf{Low}_2$ に属し、多項式階層が $\mathsf{\Sigma}_2^{\mathsf{P}} = \mathsf{\Pi}_2^{\mathsf{P}}$ に崩壊しない限り $\mathsf{NP}$ 完全にはなりえない。

使われた手法と限界

手法	達成したこと	限界
ルクスの置換群分割統治法とババイの局所証明書・デザイン補題	ジョンソングラフ上の巨大置換群 $S_k$ または $A_k$ の作用を標準的 $2$ 段階分割によって深さ $O(\log n)$ の再帰に帰着させた	$O(\log n)$ 段の再帰にわたる乗法的な分岐係数が蓄積し、計算量が $n^{O(1)}$ ではなく $n^{\operatorname{polylog}(n)}$ となる
ワイスファイラー・レマン（ $k$ - $\mathrm{WL}$ ）色細分法	ほとんどのランダムグラフおよび固定マイナーを除外するグラフに対して多項式時間で同型判定を行う	群論的な剰余類管理を伴わない純粋に組合せ論的な $k$ - $\mathrm{WL}$ では、蔡・フューラー・インマーマン（1992年）の構成したグラフにより $k = \Omega(n)$ が必要となる

未解決の問い

グラフ同型問題は $\mathsf{P}$ に属するか。すなわち決定性時間 $n^{O(1)}$ で解くことができるか。
グラフ同型問題の準多項式計算時間 $\exp(O((\log n)^c))$ における指数 $c$ を $3$ 未満、あるいは $1 + o(1)$ まで下げることができるか。

参考文献

László Babai (2016). Graph isomorphism in quasipolynomial time · DOI:10.1145/2897518.2897542 · arXiv:1512.03547
Eugene M. Luks (1982). Isomorphism of graphs of bounded valence can be tested in polynomial time · DOI:10.1016/0022-0000(82)90009-5
Uwe Schöning (1988). Graph isomorphism is in the low hierarchy · DOI:10.1016/0022-0000(88)90010-4