最大共通エッジ部分グラフ

2つのグラフが与えられた${\displaystyle G}$そして${\displaystyle G'}$最大共通辺部分グラフ問題（またはMCES問題）は、グラフを見つける問題です。${\displaystyle H}$可能な限り多くのエッジを持ち、サブグラフと同型である${\displaystyle G}$そして、${\displaystyle G'}$。

一般グラフにおける最大共通辺部分グラフ問題は、部分グラフ同型性の一般化であるためNP完全である。${\displaystyle H}$別のグラフの部分グラフと同型である${\displaystyle G}$最大共通エッジ部分グラフが${\displaystyle G}$そして${\displaystyle H}$エッジの数が同じです${\displaystyle H}$この問題は、最大クリークや最大パスなど、他のいくつかのよく知られたグラフ問題も一般化しています。^{[ 1 ]}この問題は、2 つの入力グラフが${\displaystyle G}$そして${\displaystyle G'}$頂点の数が同じである必要があります。^{[ 2 ]}

最大共通エッジ部分グラフ問題は、1981 年に Bokhari によって分散メモリ環境における並列プログラミングの応用の文脈で初めて導入されました。^{[ 2 ]}この問題は、分子構造間の類似性の尺度も提供します。^{[ 1 ]}計算生物学では、この問題はネットワークアライメントに使用され、生物学的ネットワーク間のマッピングを特定して共通のパターンを解明します。応用例としては、種間の知識伝達、タンパク質構造の比較、ヒト疾患の研究などがあります。^{[ 3 ]}生物学的応用以外の例としては、オンラインソーシャルネットワークにおけるユーザープライバシー分析や画像解析における物体認識などがあります。

MCES 問題のより厳密な変種では、共通部分グラフが連結していることが要求されます。この最大共通連結エッジ部分グラフ問題( MCCES ) は、パターン認識や化学などのアプリケーションで最も一般的に使用される定式化であり、これらのアプリケーションでは、通常、連結されていない断片を見つけることは意味がありません。^{[ 4 ]}連結性の要件は、問題が NP 完全のままであるため、一般的なグラフの計算複雑性を変更しませんが、制限されたグラフクラスの多項式時間アルゴリズムの構造に影響を与えます。^{[ 4 ]}

最大共通辺部分グラフ問題に対しては、様々なアルゴリズム的手法が開発されてきた。一つの戦略は、この問題を最大共通クリーク問題に変換することで、既存のクリーク探索アルゴリズムを利用できるようにするものである。また、制約プログラミングの手法や、実用例で発生する特定のグラフ構造に対応したヒューリスティックな手法も検討されている。

整数計画法による定式化は、2003 年の Marenco と Loiseau の研究から始まり、グラフの頂点間の適切な全単射を保証するバイナリ変数を使用して頂点の関連付けとエッジの選択を表すことから特に注目を集めています。^{[ 2 ]} 2012 年に Bahiense、Manić、Piva、および de Souza は、直接エッジ間の関連付けを表す変数を導入する BMPS 定式化を提案しました。この定式化は表現力が高く、実行可能領域が完全な次元であるという利点があります。^{[ 2 ]} Almohamad と Duffuaa による別のアプローチでは、共通部分グラフに存在しないエッジをカウントするために残差変数を使用します。^{[ 1 ]}

最近の研究では、緩和の質と計算効率のトレードオフが検討されている。対称定式化は、エッジマッピングの方向を区別することで線形計画緩和を改善するが、これには追加の変数が必要となる。縮小定式化は、変数を集約して問題のサイズを小さくし、マッピングされた頂点に接続するエッジを数えるなどの手法で解の質を維持しようとすることで、中間的な位置づけを実現している。^{[ 1 ]}

これらの整数計画法の根底にある多面体アプローチでは、関連する多面体に対して有効な不等式と面を定義する制約を特定します。これらの制約は、分岐限定法アルゴリズムに組み込むことで、解法時間を改善できます。^{[ 2 ] [ 1 ]}計算研究により、異なる定式化の相対的なパフォーマンスは入力グラフの構造に依存し、通常、より小さな定式化は探索中に1秒あたりにより多くのノードを探索しますが、線形緩和が弱くなる可能性があることが明らかになっています。^{[ 1 ]}

シミュレーテッドアニーリング法は、特に生物学的ネットワークアライメントなど、この問題の大規模なインスタンス向けに開発されてきました。これらの方法は通常、局所探索と摂動戦略を組み合わせて局所最適解から脱出します。そのようなアルゴリズムの1つは、アリコロニー最適化から応用されたフェロモンベースの摂動戦略を用いた反復局所探索を使用しており、数千の頂点を持つタンパク質間相互作用ネットワークにうまく適用されています。^{[ 3 ]}

MCCES問題は一般グラフに対してはNP困難であるが、制限されたグラフクラスに対しては多項式時間アルゴリズムが開発されている。^{[ 4 ]}

• 木構造の場合、二部グラフにおける最大重みマッチングを用いることで、この問題を多項式時間で解決できる。

• 次数が制限された外平面グラフの場合、時間計算量が の多項式時間動的計画法アルゴリズムが存在する。${\displaystyle O(n^{4D+4})}$、 どこ${\displaystyle D}$は最大頂点次数であり、${\displaystyle n}$は頂点の数です。このアルゴリズムは、「ブレード」と構成の概念を使用して、二重連結成分の分解を処理します。

• 次数が制限されているほとんどの木（各二連結成分が全域木を超える辺の数が最大で一定であるグラフ）については、多項式時間アルゴリズムが知られている。

次数が無制限の外平面グラフと次数が制限された部分 k-木の場合、問題は依然として NP 困難である。${\displaystyle k\geq 11}$[ ^{4 ]​}

注目すべきは、外平面グラフ構造が化学の応用において特に重要であることであり、NCIデータベースの化学化合物の約94%が外平面グラフ構造を持っている。^{[ 4 ]}

最大共通辺部分グラフ問題は、辺の数ではなく（誘導部分グラフにおける）頂点の数を最大化する最大共通辺部分グラフ同型性問題とは区別されるべきである。頂点数を最大化するバージョンでは、マッピングにおいて辺と非辺の両方が保存される必要がある。

多重最大共通エッジ部分グラフ問題（またはマルチMCES）は、この問題を2つ以上のグラフに一般化したものです。グラフの集合が与えられたとき、目標は、各入力グラフの部分グラフと同型で、エッジ数が最大となるグラフを見つけることです。この変種は、複数の生物学的ネットワークを同時に比較する場合、例えば、複数の種にわたる保存構造を見つける場合に特に有効です。^{[ 3 ]}

• 部分グラフ同型性問題
• 誘導部分グラフ同型性問題