部分グラフ同型性問題

{\displaystyle G} — 部分グラフが同型であるグラフ $G$ $H$

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

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

意思決定問題と計算複雑性

部分グラフ同型性がNP完全であることを証明するには、それを決定問題として定式化する必要がある。この決定問題への入力は、グラフのペアとHである。HがGの部分グラフと同型であれば、この問題の答えは肯定的であり、そうでなければ否定的である。 $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^{\prime }$

部分グラフ同型性が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) は、Ullmann のアルゴリズム VF2 をベースにした別のアルゴリズムを 2004 年に提案しました。このアルゴリズムは、さまざまなヒューリスティックを使用して改良プロセスを改善し、メモリの使用量を大幅に削減します。

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ら（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)、「定理証明手続きの複雑さ」、第3回ACM計算理論シンポジウム論文集、pp. 151– 158、doi : 10.1145/800157.805047、S2CID 7573663。
エップスタイン、デイビッド（1999）、「平面グラフにおける部分グラフ同型性と関連問題」（PDF）、グラフアルゴリズムと応用ジャーナル、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ページ。
グローガー、ハンス・ディートマー（1992）「単調グラフ特性のランダム化複雑性について」（PDF）、Acta Cybernetica、10（3）：119–127。
Han, Myoungji; Kim, Hyunjoon; Gu, Geonmo; Park, Kunsoo; Han, Wookshin (2019),効率的なサブグラフマッチング：動的プログラミング、適応型マッチング順序、およびフェイルセットの調和、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、第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)「タンパク質間相互作用ネットワークにおけるグラフレット頻度分布の効率的な推定」、Bioinformatics、22 (8): 974– 980、doi : 10.1093/bioinformatics/btl030、PMID 16452112。
Snijders, TAB; Pattison, PE; Robins, G.; Handcock, MS (2006)「指数ランダムグラフモデルの新しい仕様」、社会学的方法論、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)、「部分グラフ同型性ソルバーの実験的評価」、Graph-Based Representations in Pattern Recognition - 12th IAPR-TC-15 International Workshop、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、PMC 7314700