2つの同型グラフ
コンピュータサイエンスにおける未解決問題
グラフ同型問題は多項式時間で解決できますか?
コンピュータサイエンスにおけるさらなる未解決問題

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

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

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

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

最先端の

2015 年 11 月、László Babai は、すべてのグラフに対する準多項式時間アルゴリズム、つまり、ある固定された に対して実行時間を持つアルゴリズムを発表しました。[8] [9] [10] [11] 2017 年 1 月 4 日、Harald Helfgott が証明に欠陥を発見した後、Babai は準多項式時間の主張を撤回し、代わりに指数関数的時間境界を述べました。 2017 年 1 月 9 日、Babai は訂正を発表し (1 月 19 日に全文公開)、準多項式時間の主張を復元し、Helfgott が修正を確認しました。[12] [13] Helfgott はさらに、 c = 3とすることができるため、実行時間は2 O((log n ) 3 )であると主張しています。[14] [15]ババイは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) はグラフ同型性問題と同様の計算量限界を得ている。

解決された特殊なケース

グラフ同型性問題のいくつかの重要な特殊なケースには、効率的な多項式時間解があります。

複雑度クラス GI

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

多項式時間階層における計算量クラスに共通するが、GI内の任意の問題からその問題への多項式時間チューリング還元が存在する場合、つまり、GI 困難な問題に対する多項式時間解がグラフ同型性問題（およびGI内のすべての問題）に対する多項式時間解をもたらす場合、その問題は GI 困難であると言われる。問題がGI困難であり、かつ GI 問題に対する多項式時間解が に対する多項式時間解をもたらす場合、その問題は GIに対して完全、またはGI 完全であると言われる。

グラフ同型性問題はNPと co- AM の両方に含まれています。 GI はパリティ Pに含まれており、パリティ Pの下限値で、潜在的にずっと小さいクラスSPPにも含まれています。[35] GIがパリティ P に含まれるということは、グラフ同型性問題は、多項式時間の非決定性チューリングマシンが受け入れパスの数が偶数か奇数かを判断することよりも難しくないことを意味します。 GI はZPP NPにも含まれており、 ZPP NP の下限値です。[36]これは本質的に、NPオラクルにアクセスできる効率的なラスベガス アルゴリズムがグラフ同型性を簡単に解決できるため、定数時間でそれを行う能力が与えられてもメリットがないことを意味します。

GI完全問題とGI困難問題

他のオブジェクトの同型性

同型性の問題がGI完全問題となる数学的対象のクラスは数多く存在する。それらの中には、追加の性質や制約を与えられたグラフも含まれる。[37]

GI完全グラフクラス

グラフのクラスがGI完全であるとは、このサブクラスのグラフの同型性の認識がGI完全問題となる場合を言う。以下のクラスはGI完全である：[37]

多くの有向グラフのクラスも GI 完全です。

その他の消化管完全性の問題

同型性の問題に加えて、他の非自明な GI 完全問題も存在します。

  • グラフの自己同型群を見つける。[18]
  • グラフの自己同型性を数える。 [18]
  • グラフまたは有向グラフの自己相補性の認識。[43]
  • いわゆるMグラフのクラスに対するクリーク問題。n頂点グラフの同型性を見つけることは、サイズn 2のMグラフにおいてnクリークを見つけることと等価であることが示される。この事実は興味深い。なぜなら、サイズn 2のMグラフにおいて位数(1 − ε ) nのクリークを見つける問題は、 任意の小さな正のεに対してNP完全問題となるからである。[44]
  • 2次元複体の同相写像の問題[45]
  • 一階述語論理の定義可能性問題。この問題の入力はリレーショナルデータベースインスタンスIと関係Rであり、答えは、I上でQを評価した結果が R となるような一階述語クエリ Q（定数なし）が存在するかどうかである。[46]

消化困難な問題

  • 2つのグラフ間の同型性の個数を数える問題は、1つでも同型性が存在するかどうかを判定する問題と多項式時間で同等である。[47]
  • V-記述またはH-記述によって与えられた2つの凸多面体が射影同型かアフィン同型かを決定する問題。後者は、2つの多面体（必ずしも同じ次元ではない）を含む空間間に射影写像またはアフィン写像が存在し、それによって多面体間の一対一写像が導かれることを意味する。[42]

プログラムチェック

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

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

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

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

アプリケーション

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

ケモインフォマティクスと数理化学では、グラフ同型性検定は化学データベース内の化合物を識別するために使用されます。[49]また、有機数理化学では、グラフ同型性検定は分子グラフの生成やコンピュータ合成に役立ちます。

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

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

参照

注記

  1. ^ Kobler, Johannes; Schöning, Uwe; Torán, Jacobo (2012).グラフ同型性問題：その構造的複雑さ. Springer Science & Business Media. p. 1.
  2. ^ シェーニング（1987年）。
  3. ^ ババイ、ラスロー;エルデシュ、ポール。セルコウ、スタンリー M. (1980-08-01)。「ランダムグラフの同型性」。SIAM ジャーナル オン コンピューティング。9 (3): 628–635。土井:10.1137/0209047。ISSN  0097-5397。
  4. ^ マッケイ（1981年）。
  5. ^ ウルマン（1976年）。
  6. ^ ムーア、ラッセル、シュルマン（2008年）。
  7. ^ Endika Bengoetxea、「分布推定アルゴリズムを用いた不正確なグラフマッチング」、Ph.D.、2002年、第2章：グラフマッチング問題（2017年6月28日閲覧）
  8. ^ 「数学者が複雑性理論のブレークスルーを主張」『サイエンス』 2015年11月10日。
  9. ^ ババイ（2015）
  10. ^ 2015年の最初の講義のビデオはババイのホームページからリンクされています
  11. ^ 「グラフ同型性問題」Communications of the ACM . 2020年11月. 2021年5月4日閲覧。
  12. ^ Babai、László (2017 年 1 月 9 日)、グラフ同型性の更新
  13. ^ Erica Klarreich (2017年1月14日). 「グラフ同型性の克服 — 再び」. Quanta Magazine .
  14. ^ Helfgott、Harald (2017 年 1 月 16 日)、Isomorphismes degraphes en temps quasi-polynomial (d'après Babai et Luks, Weisfeiler-Leman...)、arXiv : 1701.04372、Bibcode :2017arXiv170104372A
  15. ^ Dona, Daniele; Bajpai, Jitendra; Helfgott, Harald Andrés (2017年10月12日). 「準多項式時間におけるグラフ同型性」. arXiv : 1710.04574 [math.GR].
  16. ^ Babai, László (2019)、「準多項式時間におけるグラフの標準形：予備報告」、Charikar, Moses、Cohen, Edith (編)、Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing、STOC 2019、Phoenix, AZ, USA、2019年6月23日～26日、Association for Computing Machinery、pp.  1237– 1246、doi :10.1145/3313276.3316356、ISBN 978-1-4503-6705-9
  17. ^ フォッジャ、サンソーネ、ヴェント (2001)。
  18. ^ abc マソン（1979年）。
  19. ^ Luks, Eugene (1993-09-01). 「順列群と多項式時間計算」. DIMACSシリーズ 離散数学および理論計算機科学第11巻. プロビデンス、ロードアイランド州: アメリカ数学会. pp.  139– 175. doi :10.1090/dimacs/011/11. ISBN 978-0-8218-6599-6. ISSN  1052-1798.
  20. ^ Algeboy (https://cs.stackexchange.com/users/90177/algeboy)、グラフ同型性と自己同型群、URL (バージョン: 2018-09-20): https://cs.stackexchange.com/q/97575
  21. ^ ケリー（1957年）。
  22. ^ アホ、ホップクロフト、ウルマン (1974)、p. 84-86。
  23. ^ ホップクロフト＆ウォン（1974年）。
  24. ^ Datta et al. (2009).
  25. ^ ab Booth & Lueker (1979)。
  26. ^ コルボーン（1981年）。
  27. ^ Muzychuk (2004).
  28. ^ ボドランダー（1990年）。
  29. ^ ミラー、1980年。フィロッティ＆メイヤー 1980年。
  30. ^ Luks (1982).
  31. ^ ババイ、グリゴリエフ、マウント (1982)。
  32. ^ ミラー（1983年）。
  33. ^ Luks (1986).
  34. ^ Booth & Colbourn 1977; Köbler, Schöning & Torán 1993.
  35. ^ コーブラー、シェーニング、トラン 1992;アルヴィンド & クルール 2006
  36. ^ Arvind & Köbler (2000).
  37. ^ abcdefghijklmnopqrstu vwx ゼムリャチェンコ、コルネンコ、ティシュケビッチ (1985)
  38. ^ ナラヤナムルシーとラビンドラン (2008)。
  39. ^ グリゴレフ (1981).
  40. ^ ガバロ、ホアキン;ガルシア、アリーナ。セルナ、マリア（2011）。 「ゲームの同型性の複雑さ」。理論的なコンピューターサイエンス。412 (48): 6675–6695。土井:10.1016/j.tcs.2011.07.022。hdl : 2117/91166。
  41. ^ ジョンソン（2005）；カイベル＆シュワルツ（2003）。
  42. ^ ab カイベル & シュワルツ (2003)。
  43. ^ コルボーン＆コルボーン（1978年）。
  44. ^ 幸善 (1978).
  45. ^ ショーテイラーとピサンスキー (1994)。
  46. ^ アリーナス＆ディアス（2016年）。
  47. ^ マトン (1979);ジョンソン、2005年。
  48. ^ Endika Bengoetxea、Ph.D.、要約
  49. ^ イルニガー（2005年）。
  50. ^ クック＆ホルダー（2007年）。
  51. ^ ベアード＆チョー（1975年）。

参考文献

  • Aho, Alfred V. ; Hopcroft, John ; Ullman, Jeffrey D. (1974)、「コンピュータアルゴリズムの設計と分析」、Reading, MA: Addison-Wesley、Bibcode :1974daca.book.....A。
  • Arvind, Vikraman; Köbler, Johannes (2000)、「グラフ同型性はZPP(NP)およびその他の低性結果において低い。」第17回計算機科学の理論的側面に関する年次シンポジウムの議事録、計算機科学の講義ノート、第1770巻、Springer-Verlag、pp. 431–442、doi :10.1007/3-540-46541-3_36、ISBN 3-540-67141-2、MR  1781752。
  • Arvind, Vikraman; Kurur, Piyush P. (2006)、「グラフ同型性はSPPに存在する」、Information and Computation、204 (5): 835– 852、doi : 10.1016/j.ic.2006.02.002、MR  2226371。
  • アリーナス、マルセロ; ディアス、ゴンサロ I. (2016)、「一階述語論理定義可能性問題の正確な計算量」、ACM Transactions on Database Systems、41 (2): 13:1–13:14、doi :10.1145/2886095。
  • ババイ、ラースロー（1980）、「強正則グラフの標準ラベル付けの複雑さについて」、SIAM Journal on Computing、9（1）：212–216、doi：10.1137/0209018、MR  0557839。
  • ババイ、ラースロー、パオロ・コデノッティ (2008)、「低ランクのハイパーグラフの同型性、中程度の指数時間で」(PDF)、第49回IEEEコンピュータサイエンス基礎シンポジウム (FOCS 2008) の議事録、IEEEコンピュータ協会、pp.  667– 676、doi :10.1109/FOCS.2008.80、ISBN 978-0-7695-3436-7、S2CID  14025744。
  • ババイ, ラースロー;グリゴリエフ, D. Yu.;マウント, David M. (1982)「限定された固有値多重度を持つグラフの同型性」, Proceedings of the 14th Annual ACM Symposium on Theory of Computing , pp.  310– 324, doi :10.1145/800070.802206, ISBN 0-89791-070-2、S2CID  12837287。
  • ババイ, ラースロー;カントール, ウィリアム;ルクス, ユージン(1983)、「計算複雑性と有限単純群の分類」、第24回計算機科学基礎シンポジウム (FOCS) の議事録、pp.  162– 171、doi :10.1109/SFCS.1983.10、ISBN 0-8186-0508-1、S2CID  6670135。
  • ババイ, ラースロー;ルクス, ユージン M. (1983)、「グラフの標準的ラベル付け」、第15回ACMコンピューティング理論シンポジウム(STOC '83)の議事録、pp.  171– 183、doi : 10.1145/800061.808746、ISBN 0-89791-099-0、S2CID  12572142。
  • Babai, László (2015),準多項式時間におけるグラフ同型性, arXiv : 1512.03547 , Bibcode :2015arXiv151203547B
  • Baird, HS; Cho, YE (1975)、「アートワークデザイン検証システム」、第12回デザインオートメーション会議（DAC '75）議事録、ピスカタウェイ、ニュージャージー州、米国：IEEE Press、pp.  414– 420。
  • Blum, Manuel ; Kannan, Sampath (1995)、「動作確認を行うプログラムの設計」、Journal of the ACM、42 (1): 269– 291、CiteSeerX  10.1.1.38.2537、doi :10.1145/200836.200880、S2CID  52151779、2017年7月5日時点のオリジナルよりアーカイブ。
  • Bodlaender, Hans (1990)、「部分k木におけるグラフ同型性と彩色インデックスのための多項式アルゴリズム」、Journal of Algorithms、11 (4): 631– 643、doi :10.1016/0196-6774(90)90013-5、MR  1079454。
  • Booth, Kellogg S.; Colbourn, CJ (1977),グラフ同型性と多項式的に同値な問題、技術報告書、vol. CS-77-04、ウォータールー大学コンピュータサイエンス学部。
  • Booth, Kellogg S.; Lueker, George S. (1979)、「区間グラフ同型性を決定するための線形時間アルゴリズム」、Journal of the ACM、26 (2): 183– 195、doi : 10.1145/322123.322125、MR  0528025、S2CID  18859101。
  • Boucher, C.; Loker, D. (2006), パーフェクトグラフおよびパーフェクトグラフのサブクラスのグラフ同型完全性(PDF)、技術レポート、vol. CS-2006-32、ウォータールー大学コンピュータサイエンス学部。
  • チョン、ファン・RK（1985）、「木のカット幅と位相帯域幅について」、SIAM Journal on Algebraic and Discrete Methods、6（2）：268– 277、doi：10.1137/0606026、MR  0778007。
  • Colbourn, CJ (1981)、「順列グラフの同型性検定について」、Networks、11 : 13– 21、doi :10.1002/net.3230110103、MR  0608916。
  • コルボーン、マーリーン・ジョーンズ;コルボーン、チャールズ・J. (1978)、「グラフ同型性と自己相補グラフ」、ACM SIGACT News、10 (1): 25– 29、doi :10.1145/1008605.1008608、S2CID  35157300。
  • Cook, Diane J.; Holder, Lawrence B. (2007)、「Section 6.2.1: Canonical Labeling」、Mining Graph Data、Wiley、pp.  120– 122、ISBN 978-0-470-07303-2。
  • Datta, S.; Limaye, N.; Nimbhorkar, P.; Thierauf, T.; Wagner, F. (2009)「平面グラフ同型性は対数空間にある」、2009 24th Annual IEEE Con​​ference on Computational Complexity、p. 203、arXiv : 0809.2319、doi :10.1109/CCC.2009.16、ISBN 978-0-7695-3717-7、S2CID  14836820。
  • Filotti, IS; Mayer, Jack N. (1980)、「固定種数のグラフの同型性を決定する多項式時間アルゴリズム」、第12回ACM計算理論シンポジウム論文集、pp.  236– 243、doi :10.1145/800141.804671、ISBN 0-89791-017-6、S2CID  16345164。
  • Foggia, P.; Sansone, C.; Vento, M. (2001)、「グラフ同型性のための5つのアルゴリズムの性能比較」（PDF）、Proc. 3rd IAPR-TC15 Workshop Graph-Based Representations in Pattern Recognition、pp.  188– 199、 2015年9月24日にオリジナル（PDF）からアーカイブ、 2009年12月18日取得。
  • ゲイリー、マイケル・R. ;ジョンソン、デイビッド・S. (1979)、「コンピュータとイントラクタビリティ：NP完全性理論へのガイド」、WHフリーマン、ISBN 978-0-7167-1045-5。
  • グリゴレフ、D.Ju。 (1981)、「「野生の」行列問題と代数とグラフの同型性の複雑さ」、Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta imeni VA Steklova Akademii Nauk SSSR (LOMI) (ロシア語)、105 : 10–17、198、MR  0628981. 英語訳はJournal of Mathematical Sciences 22 (3): 1285–1289, 1983に掲載されています。
  • ホップクロフト、ジョン、ウォン、J. (1974)、「平面グラフの同型性のための線形時間アルゴリズム」、第6回ACMコンピューティング理論シンポジウム論文集、pp.  172– 184、doi :10.1145/800119.803896、S2CID  15561884。
  • Irniger、Christophe-André Mario (2005)、「グラフ マッチング: 機械学習を使用したグラフ データベースのフィルタリング」、Dissertationen zur künstlichen Intelligenz、vol. 293、別名、ISBN 1-58603-557-6。
  • Kaibel, Volker; Schwartz, Alexander (2003)、「多面体同型問題の複雑さについて」、Graphs and Combinatorics、19 (2): 215– 230、arXiv : math/0106093、doi :10.1007/s00373-002-0503-y、MR  1996205、S2CID  179936、2015年7月21日時点のオリジナルよりアーカイブ。
  • ケリー、ポール・J. (1957)、「木の合同定理」、パシフィック・ジャーナル ・オブ・マスマティクス、7 : 961–968、doi : 10.2140/pjm.1957.7.961、MR0087949。
  • Köbler, Johannes; Schöning, Uwe ; Torán, Jacobo (1992)、「PPにおけるグラフ同型性は低い」、Computational Complexity、2 (4): 301– 330、doi :10.1007/BF01200427、MR  1215315、S2CID  8542603。
  • コーゼン、デクスター（1978）、「グラフ同型性と等価なクリーク問題」、ACM SIGACT News、10（2）：50–52、doi：10.1145/990524.990529、S2CID  52835766。
  • Luks, Eugene M. (1982)、「有界価数グラフの同型性は多項式時間で検証できる」、Journal of Computer and System Sciences、25 : 42– 65、doi : 10.1016/0022-0000(82)90009-5、MR  0685360、S2CID  2572728。
  • Luks, Eugene M. (1986)、「順列群とグラフ同型性のための並列アルゴリズム」、Proc. IEEE Symp. Foundations of Computer Science、pp.  292– 302。
  • マソン、ルドルフ（1979）、「グラフ同型性カウント問題に関するノート」、情報処理レター、8（3）：131-132、doi：10.1016/0020-0190（79）90004-8、MR  0526453。
  • McKay, Brendan D. (1981), 「実用グラフ同型性」,第10回マニトバ数値数学・計算会議 (ウィニペグ, 1980) , Congressus Numerantium, vol. 30, pp.  45– 87, MR  0635936。
  • ミラー、ゲイリー（1980）、「有界種数グラフの同型性テスト」、第12回ACMコンピューティング理論シンポジウムの議事録、pp.  225– 235、doi：10.1145/800141.804670、ISBN 0-89791-017-6、S2CID  13647304。
  • ミラー、ゲイリー・L. (1983)、「k-縮約可能グラフの同型性テストと標準形（有界価数と有界種数の一般化）」、コンピュータ理論の基礎に関する国際会議会議論文集、コンピュータサイエンスの講義ノート、第158巻、pp.  310– 327、doi :10.1007/3-540-12689-9_114、ISBN 978-3-540-12689-8.情報制御 56 (1–2):1–20、1983年に掲載された論文全文。
  • ムーア、クリストファー、ラッセル、アレクサンダー、シュルマン、レナード J. (2008)、「対称群は強フーリエサンプリングに反する」、SIAM Journal on Computing、37 (6): 1842– 1864、arXiv : quant-ph/0501056、doi :10.1137/050644896、MR  2386215、S2CID  9550284。
  • Muzychuk, Mikhail (2004)、「循環グラフの同型性問題の解法」、Proc. London Math. Soc.、88 : 1– 41、doi :10.1112/s0024611503014412、MR  2018956、S2CID  16704931。
  • Narayanamurthy, SM; Ravindran, B. (2008)「マルコフ決定過程における対称性の発見の難しさについて」（PDF）、第25回国際機械学習会議（ICML 2008）の議事録、pp.  688– 696。
  • Schmidt, Douglas C.; Druffel, Larry E. (1976)、「距離行列を用いた有向グラフの同型性判定のための高速バックトラッキングアルゴリズム」、Journal of the ACM、23 (3): 433– 445、doi : 10.1145/321958.321963、MR  0411230、S2CID  6163956。
  • Schöning, Uwe (1987)、「グラフ同型性は低階層にある」、第4回計算機科学の理論的側面に関する年次シンポジウムの議事録、pp.  114– 124; また、Journal of Computer and System Sciences 37 :312–323, 1988を参照。
  • Shawe-Taylor, John; Pisanski, Tomaž (1994)、「2次元複体の同相写像はグラフ同型完全である」、SIAM Journal on Computing、23 (1): 120– 132、doi :10.1137/S0097539791198900、MR  1258998。
  • スピルマン、ダニエル・A.（1996）「強正則グラフの同型性テストの高速化」第28回ACMコンピューティング理論シンポジウム（STOC '96）の議事録、ACM、pp.  576– 584、ISBN 978-0-89791-785-8。
  • ウルマン、ジュリアン・R. (1976)、「部分グラフ同型性のためのアルゴリズム」（PDF）、Journal of the ACM、23 : 31–42、CiteSeerX  10.1.1.361.7741、doi :10.1145/321921.321925、MR  0495173、S2CID  17268751。

調査とモノグラフ

  • リード、ロナルド・C.;コルニール、デレク・G. (1977)、「グラフ同型病」、グラフ理論ジャーナル、1 (4): 339– 363、doi :10.1002/jgt.3190010410、MR  0485586、S2CID  26589776。
  • Gati, G. (1979)、「同型病に関するさらなる注釈付き参考文献」、Journal of Graph Theory、3 (2): 95– 109、doi :10.1002/jgt.3190030202。
  • Zemlyachenko, VN; Korneenko, NM; Tyshkevich, RI (1985)、「グラフ同型性問題」、Journal of Mathematical Sciences、29 (4): 1426– 1481、doi : 10.1007/BF02104746、S2CID  121818465。 ( Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. VA Steklova AN SSSR (ソ連科学アカデミーのステクロフ数学研究所レニングラード部門のセミナーの記録)、Vol. 118、pp. 83–158、1982から翻訳。)
  • Arvind, V.; Torán, Jacobo ( 2005)、「同型性テスト：展望と未解決問題」（PDF）、欧州理論計算機科学協会紀要、86 : 66–84（グラフ、環、群の同型性問題に関連する未解決の問題の簡単な調査。）
  • ケブラー、ヨハネス。シェーニング, ウーヴェ;トラン、ヤコボ (1993)、「グラフ同型問題: その構造的複雑性」、Birkhäuser、ISBN 978-0-8176-3680-7(本の表紙より: この本は、問題の計算複雑性の問題に焦点を当てており、NP クラスや他の複雑性クラスにおける問題の相対的な位置をより深く理解できる最近の結果をいくつか紹介しています。)
  • ジョンソン、デイビッド・S. (2005)、「NP完全性コラム」、ACM Transactions on Algorithms、1 (1): 160– 176、doi :10.1145/1077464.1077476、S2CID  12604799（このコラムの第 24 版では、書籍「Computers and Intractability」および以前のコラムで取り上げた未解決の問題、特にグラフ同型性に関する最新の状況について説明します。）
  • Torán, Jacobo; Wagner, Fabian (2009)「平面グラフ同型性の複雑さ」（PDF）、Bulletin of the European Association for Theoretical Computer Science、97 、 2010年9月20日にオリジナル（PDF）からアーカイブ、 2010年6月3日取得。
  • ストイチェフ、ストイチョ D. (2019)、「グラフ自己同型群とグラフ同型性のための新しい正確かつヒューリスティックなアルゴリズム」、Journal of Experimental Algorithmics、24 : 1– 27、doi :10.1145/3333250、S2CID  202676274。

ソフトウェア

  • グラフ同型性、実装のレビュー、Stony Brook アルゴリズム リポジトリ。