グラフ同型性問題

グラフ同型性問題とは、2 つの有限グラフが同型であるかどうかを判定する計算問題である。^{[ 1 ]}

この問題は多項式時間で解けることもNP完全であることも知られておらず、したがって計算複雑性クラスNP中間に属する可能性がある。グラフ同型問題はNPクラスの低階層に属することが知られており、これは多項式時間階層が第2レベルに縮退しない限りNP完全ではないことを意味する。 ^{[ 2 ]} 同時に、多くの特殊なグラフクラスの同型性は多項式時間で解くことができ、実際にはグラフ同型性は効率的に解けることが多い。^{[ 3 ] [ 4 ]}

この問題は、与えられたグラフGが別の与えられたグラフHと同型な部分グラフを含むかどうかを問う部分グラフ同型性問題^{[ 5 ]}の特殊なケースです。この問題は NP 完全であることが知られています。また、対称群上の非可換隠れ部分群問題の特殊なケースであることも知られています。^{[ 6 ]}

画像認識の分野では、これは正確なグラフマッチング問題として知られています。^{[ 7 ]}

2015年11月、ラースロー・ババイは、すべてのグラフに対して準多項式時間アルゴリズム、すなわち実行時間が のアルゴリズムを発表した。$2^O((\log n)^c)$ある固定値に対して${\displaystyle c>0}$[ ^{8 ] [ 9 ] [ 10 ] [ 11 ]} 2017年1月4日、Babaiは準多項式主張を撤回し、代わりに指数関数以下の時間制限を述べた。これは^、 Harald Helfgottが証明の欠陥を発見したためである。2017年1月9日、Babaiは訂正を発表し（1月19日に全文公開）、準多項式主張を復活させた。Helfgottは修正を確認した。^{[ 12 ] [ 13 ]} Helfgottはさらに、 c = 3とすれば実行時間は2 ^{O((log n ) 3 )}になると主張している。^{[ 14 ] [ 15 ]} Babaiは、2019年の理論計算シンポジウムで関連研究の「予備報告」を発表し、グラフ正規化のための準多項式アルゴリズムについて説明したが、^{[ 16 ]} 2025年現在これらのアルゴリズムの完全版は未公開のままである。

これ以前に最も広く受け入れられていた理論的アルゴリズムは、Babai & Luks (1983)によるもので、Luks (1982)の以前の研究とVN Zemlyachenko ( Zemlyachenko, Korneenko & Tyshkevich 1985 )のサブ階乗アルゴリズムを組み合わせたものに基づいていた。このアルゴリズムは、 n個の頂点を持つグラフに対して2 ^{O( √ n log n )の実行時間を持ち、}有限単純群の分類に依存している。この分類定理がない場合、わずかに弱い上限 2 ^{O( √ n log 2 n )}が最初に強正則グラフに対してLászló Babai ( 1980 )によって得られ、その後Babai & Luks (1983 )によって一般グラフに拡張された。強正則グラフの指数√ nの改善はSpielman (1996 )によって行われた。有界ランクのハイパーグラフについては、グラフの場合と一致する準指数的な上限がBabai & Codenotti (2008)によって得られた。     

グラフ同型性判定のための実用的なアルゴリズムはいくつかあり、例えばMcKay (1981)、Schmidt & Druffel (1976)、Ullman (1976)、Stoichev (2019)によるものなどがある。これらのアルゴリズムはランダムグラフでは良好なパフォーマンスを示すようだが、最悪の場合、指数関数的な時間パフォーマンスになるという大きな欠点がある。^{[ 17 ]}

グラフ同型問題は、グラフの自己同型群を計算する問題と計算上同等であり、 ^{[ 18 ] [ 19 ] [ 20 ]}置換群同型問題や置換群交差問題よりも弱い。後者の2つの問題については、Babai、Kantor 、 Luks（1983）がグラフ同型問題と同様の計算量の上限を得た。

グラフ同型性問題の重要な特殊ケースのいくつかは、効率的な多項式時間解法を持つ。

• 樹木^{[ 21 ] [ 22 ]}
• 平面グラフ^{[ 23 ]} (実際、平面グラフ同型性は対数空間にあり、^{[ 24 ]} Pに含まれるクラスです)
• 区間グラフ^{[ 25 ]}
• 順列グラフ^{[ 26 ]}
• 巡回グラフ^{[ 27 ]}
• パラメータ制限付きグラフ
  • 木幅が制限されたグラフ^{[ 28 ]}
  • 有界種数のグラフ^{[ 29 ]}（平面グラフは種数0のグラフです。）
  • 次数が制限されたグラフ^{[ 30 ]}
  • 固有値の重複度が制限されたグラフ^{[ 31 ]}
  • k-縮約可能グラフ（有界次数と有界種数の一般化）^{[ 32 ]}
  • 色の多重度が制限された（つまり、固定されたkに対して、同じ色を持つ頂点が最大でk個しかない）有色グラフの色保存同型性は、クラスNCに属し、これはPのサブクラスである。^{[ 33 ]}

グラフ同型問題はNP完全であることも、扱いやすいことも知られていないため、研究者たちは、グラフ同型問題への多項式時間チューリング還元を持つ問題の集合である新しいクラスGIを定義することで、この問題についての洞察を得ようとしてきた。 ^{[ 34 ]}実際にグラフ同型問題が多項式時間で解ける場合、GIはPに等しくなる。一方、問題がNP完全であれば、GIはNPに等しくなり、 NPのすべての問題は準多項式時間で解けることになる。

多項式時間階層内の複雑性クラスに共通する慣例として、GI内の任意の問題からその問題への多項式時間チューリング還元が存在する場合、その問題はGI-ハードと呼ばれます。つまり、GI-ハード問題に対する多項式時間解は、グラフ同型性問題 (したがってGI内のすべての問題) に対する多項式時間解をもたらします。${\displaystyle X}$は、GI 困難であり、かつ GI 問題の多項式時間解が の多項式時間解をもたらす場合、GIに対して完全、またはGI-完全であると呼ばれます。${\displaystyle X}$。

グラフ同型性問題は、NPと co- AM の両方に含まれています。 GI は、パリティ Pに対して含まれ、低レベルであり、潜在的にはるかに小さいクラスSPPにも含まれています。^{[ 35 ]}パリティ P に属するということは、グラフ同型性問題は、多項式時間非決定性チューリング マシンが受理パスの数が偶数か奇数かを判定することよりも難しくないことを意味します。 GI は、 ZPP ^NPに対しても含まれ、低レベルです。^{[ 36 ]}これは基本的に、NPオラクルにアクセスできる効率的なラスベガス アルゴリズムは、グラフ同型性を非常に簡単に解決できるため、定数時間で解決する能力を与えられても、その能力が向上しないことを意味します。

マヌエル・ブルムとサンパス・カンナン（1995 ）は、グラフ同型性をチェックするプログラムの確率的チェッカーを示した。Pは、2つのグラフが同型であるかどうかをチェックする多項式時間手順であると主張されているが、信頼されていない。グラフGとHが同型であるかどうかをチェックするには、次の手順を実行する。 

• Pに、 GとHが同型 かどうかを尋ねてください。
  • 答えが「はい」の場合：
    • Pをサブルーチンとして使用して同型写像を構築します。Gの頂点uとHの頂点vをマークし、グラフを（小さな局所的な変更を加えて）区別できるように修正します。修正したグラフが同型であるかどうかをPに問い合わせます。同型でない場合は、 vを別の頂点に変更します。探索を続けます。
    • 同型写像が見つかる（そして検証できる）か、そうでなければPは自己矛盾を起こすかのどちらかである。
  • 答えが「いいえ」の場合：
    • 以下の手順を100回繰り返します。グラフGまたはHをランダムに選択し、その頂点をランダムに並べ替えます。グラフPがGとHに同型であるかどうかをPに尋ねます。（グラフの非同型性に関するAMプロトコルと同様です。）
    • いずれかのテストが失敗した場合は、Pを無効なプログラムと判断します。そうでない場合は、「いいえ」と答えます。

この手順は多項式時間で実行でき、 P がグラフ同型性に関する正しいプログラムであれば正しい答えを返します。Pが正しいプログラムではないが、GとHに対して正しい答えを返す場合、チェッカーは正しい答えを返すか、Pの不正な動作を検出します。Pが正しいプログラムではなく、GとHに対して誤った答えを返す場合、チェッカーは高い確率でPの不正な動作を検出するか、2 ⁻¹⁰⁰の確率で誤った答えを返します。

特に、Pはブラックボックスとしてのみ使用される。

グラフは、コンピュータビジョンやパターン認識など多くの分野で構造情報を符号化するために一般的に使用されており、グラフマッチング、つまりグラフ間の類似性の識別は、これらの分野における重要なツールです。これらの分野では、グラフ同型問題は厳密なグラフマッチングとして知られています。^{[ 48 ]}

化学情報学や数理化学では、グラフ同型性テストは化学データベース内の化学化合物を識別するために使用されています。^{[ 49 ]}また、有機数理化学では、グラフ同型性テストは分子グラフの生成やコンピュータ合成に役立ちます。

化学データベース検索は、グラフ正規化アプローチがよく使用されるグラフィカルデータマイニングの一例です。 ^{[ 50 ]}特に、分子情報を標準的かつ人間が読みやすい方法でエンコードし、データベースやウェブ上でそのような情報を検索しやすくするために設計された、 SMILESやInChIなどの化学物質の識別子の多くは、計算に正規化ステップを使用しており、これは基本的に分子を表すグラフの正規化です。^{[ 51 ]}

電子設計自動化において、グラフ同型性はレイアウト対回路図（LVS）回路設計ステップの基礎であり、回路図と集積回路レイアウトで表される電気回路が同じかどうかを検証するものである。 ^{[ 52 ]}

• グラフ自己同型性問題
• グラフ正規化