部分グラフ同型性問題

理論計算機科学において、部分グラフ同型性問題は、2つのグラフ GとHが入力として与えられ、GにHと同型の部分グラフが含まれているかどうかを判定する計算タスクである。部分グラフ同型性は、最大クリーク問題とグラフにハミルトン閉路が含まれているかどうかをテストする問題の一般化であり、したがってNP完全である。^[1]ただし、部分グラフ同型の他の特定のケースは、多項式時間で解決できる場合がある。^[2]

同じ問題に対して、サブグラフマッチングという名前が使用されることもあります。この名前は、単なる決定問題ではなく、そのようなサブグラフを見つけることに重点を置いています。

決定問題と計算の複雑さ

サブグラフ同型性が NP 完全であることを証明するには、それを決定問題として定式化する必要があります。決定問題への入力は、グラフGとHのペアです。問題の答えは、H がGのサブグラフに同型である場合は肯定的であり、そうでない場合は否定的です。

正式な質問:

をグラフとします。となるサブグラフは存在しますか? つまり、となるような一対一変換は存在しますか? $G=(V,E)$ $H=(V^{\prime },E^{\prime })$ $G_{0}=(V_{0},E_{0})\mid V_{0}\subseteq V,E_{0}\subseteq E\cap (V_{0}\times V_{0})$ $G_{0}\cong H$ $f\colon V_{0}\rightarrow V^{\prime}$ $\{\,v_{1},v_{2}\,\}\in E_{0}\iff \{\,f(v_{1}),f(v_{2})\,\ }\in E^{\プライム }$

部分グラフ同型性が NP 完全であることの証明は単純で、クリーク問題の簡約に基づいています。クリーク問題は NP 完全決定問題であり、入力は単一のグラフGと数kで、問題はGがk頂点を持つ完全な部分グラフを含むかどうかです。これを部分グラフ同型性問題に置き換えるには、単にH を完全グラフK _kとします。すると、 GとHの部分グラフ同型性問題の答えは、Gとkのクリーク問題の答えに等しくなります。クリーク問題は NP 完全であるため、この多項式時間の多対一簡約は、部分グラフ同型性も NP 完全であることを示しています。^[3]

ハミルトン閉路問題の別の帰着は、ハミルトン性をテストするグラフG をグラフGとHのペアに変換する。ここで、HはGと同じ数の頂点を持つ閉路である。ハミルトン閉路問題は平面グラフの場合でも NP 完全であるため、これは部分グラフ同型性が平面グラフの場合でも NP 完全であることを示している。^[4]

部分グラフ同型性は、 G がHと同型かどうかを問うグラフ同型性問題の一般化です。グラフ同型性問題の答えは、GとH の両方に同じ数の頂点と辺があり、 GとHの部分グラフ同型性問題が真である場合にのみ真になります。ただし、グラフ同型の複雑性理論的地位は未解決の問題のままです。

単調グラフ特性のクエリ複雑性に関するAanderaa-Karp-Rosenberg予想の文脈において、Gröger (1992)は、任意のサブグラフ同型性問題にはクエリ複雑性Ω( n ^3/2 )があることを示した。つまり、サブグラフ同型性を解くには、入力にグラフ内のΩ( n ^3/2 )の異なるエッジが存在するかどうかをチェックするアルゴリズムが必要である。^[5]

アルゴリズム

Ullmann (1976) は、部分グラフ同型性を解くための再帰的なバックトラッキング手順について説明しています。その実行時間は一般に指数関数的ですが、Hの任意の固定選択に対して多項式時間かかります(多項式はHの選択に依存します)。Gが平面グラフ(またはより一般的には有界展開のグラフ) でHが固定されている場合、部分グラフ同型性の実行時間は線形時間に短縮できます。^[2]

Ullmann (2010) は、1976 年のサブグラフ同型アルゴリズムの論文を大幅に更新したものです。

Cordella (2004) は、2004 年に Ullmann のアルゴリズム VF2 をベースにした別のアルゴリズムを提案しました。このアルゴリズムは、さまざまなヒューリスティックを使用して改良プロセスを改善し、使用するメモリを大幅に削減します。

Bonnici & Giugno (2013) は、いくつかのヒューリスティックを使用して頂点の初期順序を改善する、より優れたアルゴリズムを提案しました。

中規模で難しいインスタンスに対する現在の最先端のソルバーは、グラスゴーサブグラフソルバー（McCreesh、Prosser、Trimble（2020））です。^[6]このソルバーは、制約プログラミングアプローチを採用しており、ビット並列データ構造と特殊な伝播アルゴリズムを使用してパフォーマンスを向上させます。問題の最も一般的なバリエーションをサポートし、ソリューションをカウントまたは列挙したり、ソリューションが存在するかどうかを判断したりできます。

大規模グラフの場合、最先端のアルゴリズムには CFL-Match や Turboiso があり、Han ら (2019) による DAF などの拡張版もあります。

アプリケーション

サブグラフ同型性は化学情報学の分野で、化合物の構造式から類似性を見つけるために応用されており、この分野ではサブ構造検索という用語がよく使用されます。^[7]クエリ構造は、多くの場合、構造エディタプログラムを使用してグラフィカルに定義されます。SMILESベースのデータベースシステムでは、通常、SMILESの拡張機能であるSMARTSを使用してクエリを定義します。

グラフHの同型コピーの数をより大きなグラフG内で数えるという密接に関連した問題は、データベースにおけるパターン発見^[8] 、タンパク質間相互作用ネットワークのバイオインフォマティクス[9]、およびソーシャル^{ネットワーク}を数学的にモデル化する指数ランダムグラフ法^[10]に適用されてきました。

Ohlrich ら (1993) は、電子回路のコンピュータ支援設計におけるサブグラフ同型性の応用について説明しています。サブグラフマッチングはグラフ書き換え(最も実行時間を要する)のサブステップでもあるため、グラフ書き換えツールによって提供されます。

この問題は人工知能でも関心を集めており、グラフ問題におけるパターンマッチングの配列の一部であると考えられています。また、グラフマイニングとして知られるサブグラフ同型性の拡張もこの分野で関心を集めています。^[11]

参照

注記

^ Cook-Levinの定理を証明するオリジナルのCook (1971)の論文では、クリークを含む3-SATからの還元を使用して、サブグラフ同型性がNP完全であることがすでに示されていました。
^ エップスタイン (1999);ネシェトジル & オッソナ・デ・メンデス (2012)
^ Wegener, Ingo (2005)、複雑性理論：効率的なアルゴリズムの限界を探る、Springer、p. 81、ISBN 9783540210450。
^ de la Higuera, Colin; Janodet, Jean-Christophe; Samuel, Émilie; Damiand, Guillaume; Solnon, Christine (2013)、「Polynomial algorithms for open plane graph and subgraph isomorphisms」(PDF)、Theoretical Computer Science、498 : 76–99、doi : 10.1016/j.tcs.2013.05.026、MR 3083515、1970 年代半ばから、同型性問題は平面グラフに対して多項式時間で解けることが知られています。しかし、特にハミルトン閉路問題が平面グラフに対して NP 完全であるため、部分同型性問題は依然として N P 完全であることも指摘されています。
^ ここで Ω はビッグオメガ表記を呼び出します。
^ 実験的評価については、Solnon (2019) を参照してください。
^ ウルマン（1976）
^ 倉持・カリピス（2001年）。
^ Pržulj、Corneil、Jurisica（2006年）。
^ Snijders et al. (2006).
^ http://www.aaai.org/Papers/Symposia/Fall/2006/FS-06-02/FS06-02-007.pdf; 拡大版は https://e-reports-ext.llnl.gov/pdf/332302.pdf を参照

参考文献

Cook, SA (1971)、「定理証明手順の複雑さ」、Proc. 3rd ACM Symposium on Theory of Computing、pp. 151–158、doi : 10.1145/800157.805047、S2CID 7573663。
エップスタイン、デイビッド(1999)、「平面グラフにおけるサブグラフ同型性と関連問題」(PDF)、Journal of Graph Algorithms and Applications、3 (3): 1–27、arXiv : cs.DS/9911003、doi :10.7155/jgaa.00014、S2CID 2303110。
ゲイリー、マイケル・R. ;ジョンソン、デビッド・S. (1979)、「コンピュータと扱いにくさ：NP完全性理論へのガイド」、WHフリーマン、ISBN 978-0-7167-1045-5A1.4: GT48、202ページ。
Groger, Hans Dietmar (1992)、「単調グラフ特性のランダム化複雑性について」(PDF)、Acta Cybernetica、10 (3): 119–127。
Han, Myoungji; Kim, Hyunjoon; Gu, Geonmo; Park, Kunsoo; Han, Wookshin (2019)、「効率的なサブグラフマッチング：動的プログラミング、適応型マッチング順序、およびフェイルセットの調和」、SIGMOD、doi :10.1145/3299869.3319880、S2CID 195259296
倉持道弘、カリピスジョージ (2001)、「頻繁なサブグラフの発見」、第 1 回 IEEE 国際データマイニング会議、p. 313、CiteSeerX 10.1.1.22.4992、doi :10.1109/ICDM.2001.989534、ISBN 978-0-7695-1119-1、S2CID 8684662。
Ohlrich, Miles; Ebeling, Carl; Ginting, Eka; Sather, Lisa (1993)、「SubGemini: 高速サブグラフ同型アルゴリズムを使用したサブ回路の識別」、第 30 回国際設計自動化会議の議事録、pp. 31–37、doi : 10.1145/157485.164556、ISBN 978-0-89791-577-9、S2CID 5889119。
Nešetřil, Jaroslav ; Ossona de Mendez, Patrice (2012)、「18.3 サブグラフ同型性問題とブールクエリ」、Sparsity: Graphs, Structures, and Algorithms、Algorithms and Combinatorics、vol. 28、Springer、pp. 400–401、doi :10.1007/978-3-642-27875-4、ISBN 978-3-642-27874-7、MR 2920058。
Pržulj, N.; Corneil, DG ; Jurisica, I. (2006)、「タンパク質間相互作用ネットワークにおけるグラフレット頻度分布の効率的な推定」、バイオインフォマティクス、22 (8): 974–980、doi : 10.1093/bioinformatics/btl030、PMID 16452112。
Snijders, TAB; Pattison, PE; Robins, G.; Handcock, MS (2006)、「指数ランダムグラフモデルの新しい仕様」、Sociological Methodology、36 (1): 99–153、CiteSeerX 10.1.1.62.7975、doi :10.1111/j.1467-9531.2006.00176.x、S2CID 10800726。
ウルマン、ジュリアン R. (1976)、「サブグラフ同型性アルゴリズム」、Journal of the ACM、23 (1): 31–42、doi : 10.1145/321921.321925、S2CID 17268751。
ジャミル、ハサン (2011)、「構造的統一と最小グラフ構造を使用したサブグラフ同型クエリの計算」、第 26 回 ACM 応用コンピューティングシンポジウム、pp. 1058–1063。
ウルマン、ジュリアン R. (2010)、「バイナリ制約充足とサブグラフ同型性のためのビットベクトルアルゴリズム」、Journal of Experimental Algorithmics、15 : 1.1、CiteSeerX 10.1.1.681.8766、doi :10.1145/1671970.1921702、S2CID 15021184。
Cordella, Luigi P. (2004)、「大規模グラフのマッチングのための (サブ) グラフ同型性アルゴリズム」、IEEE Transactions on Pattern Analysis and Machine Intelligence、26 (10): 1367–1372、CiteSeerX 10.1.1.101.5342、doi :10.1109/tpami.2004.75、PMID 15641723、S2CID 833657
Bonnici, V.; Giugno, R. (2013)、「サブグラフ同型性アルゴリズムと生化学データへのその応用」、BMC Bioinformatics、14(Suppl7) (13): S13、doi : 10.1186/1471-2105-14-s7-s13、PMC 3633016、PMID 23815292
Carletti, V.; Foggia, P.; Saggese, A.; Vento, M. (2018)、「VF3 による巨大で密なグラフの正確なサブグラフ同型性の時間計算量への挑戦」、IEEE Transactions on Pattern Analysis and Machine Intelligence、40 (4): 804–818、doi :10.1109/TPAMI.2017.2696940、PMID 28436848、S2CID 3709576
Solnon, Christine (2019)、「サブグラフ同型性ソルバーの実験的評価」(PDF)、パターン認識におけるグラフベース表現 - 第 12 回 IAPR-TC-15 国際ワークショップ、GbRPR 2019、トゥール、フランス、2019 年 6 月 19 ～ 21 日、議事録、Lecture Notes in Computer Science、vol. 11510、Springer、pp. 1 ～ 13、doi :10.1007/978-3-030-20081-7_1、ISBN 978-3-030-20080-0、S2CID 128270779
McCreesh, Ciaran; Prosser, Patrick; Trimble, James (2020)、「The Glasgow Subgraph Solver: Using Constraint Programming to Tackle Hard Subgraph Isomorphism Problem Variants」、グラフ変換 - 第 13 回国際会議、ICGT 2020、STAF 2020 の一環として開催、ノルウェー、ベルゲン、2020 年 6 月 25 ～ 26 日、議事録、Lecture Notes in Computer Science、vol. 12150、Springer、pp. 316 ～ 324、doi : 10.1007/978-3-030-51372-6_19、ISBN 978-3-030-51371-9

[1] Cook-Levinの定理を証明するオリジナルのCook (1971)の論文では、クリークを含む3-SATからの還元を使用して、サブグラフ同型性がNP完全であることがすでに示されていました。

[e99-2] エップスタイン (1999);ネシェトジル & オッソナ・デ・メンデス (2012)

[3] Wegener, Ingo (2005)、複雑性理論：効率的なアルゴリズムの限界を探る、Springer、p. 81、ISBN 9783540210450。

[4] Higuera, Colin; Janodet, Jean-Christophe; Samuel, Émilie; Damiand, Guillaume; Solnon, Christine (2013)、「Polynomial algorithms for open plane graph and subgraph isomorphisms」(PDF)、Theoretical Computer Science、498 : 76–99、doi : 10.1016/j.tcs.2013.05.026、MR 3083515、1970 年代半ばから、同型性問題は平面グラフに対して多項式時間で解けることが知られています。しかし、特にハミルトン閉路問題が平面グラフに対して NP 完全であるため、部分同型性問題は依然として N P 完全であることも指摘されています。

[5] ここで Ω はビッグオメガ表記を呼び出します。

[6] 実験的評価については、Solnon (2019) を参照してください。

[7] ウルマン（1976）

[8] 倉持・カリピス（2001年）。

[9] Pržulj、Corneil、Jurisica（2006年）。

[10] Snijders et al. (2006).

[11] ttp://www.aaai.org/Papers/Symposia/Fall/2006/FS-06-02/FS06-02-007.pdf; 拡大版は https://e-reports-ext.llnl.gov/pdf/332302.pdf を参照