Maximum common induced subgraph とは

グラフ理論と理論計算科学では、2つのグラフGとHの最大共通誘導部分グラフは、GとHの誘導部分グラフであり、可能な限り多くの頂点を持つグラフです。
このグラフを見つけることはNP困難です。関連する決定問題では、入力は2つのグラフGおよびHと数kである。問題は、GとHが少なくともk個の頂点を有する共通誘導部分グラフを有するかどうかを決定することである。この問題はNP完全です。これは、kがGとHのうちの小さい方の頂点の数に等しいときに生じる、誘導された部分グラフ同型写像問題の一般化です。このグラフ全体は、他のグラフの誘導部分グラフとして現れなければなりません。
最大独立集合問題に対する近似結果の硬さに基づいて、最大共通誘導サブグラフ問題も近似することは困難である。これは、P = NPでなければ、 n {\displaystyle n} – 頂点グラフ上の多項式時間で、任意の ϵ > 0 {\displaystyle \epsilon >0} に対して、最適の因数 n 1 ϵ {\displaystyle n^{1-\epsilon }} 内の解を常に見つける近似アルゴリズムは存在しないことを意味する。
この問題の1つの可能な解は、GとHのモジュラ積グラフを作成することです。このグラフでは、最大クリークはGとHの最大共通誘導部分グラフに対応しています。最大共通誘導サブグラフ。
最大共通誘導サブグラフアルゴリズムは、ケミンフォーマットおよびファルマコフォアマッピングにおいて長い伝統を有する。