Maximum common edge subgraph とは

2つのグラフ G {\displaystyle G} G {\displaystyle G’} が与えられたとき、最大共通エッジ部分グラフ問題は、 G {\displaystyle G} の部分グラフと G {\displaystyle G’} の部分グラフの両方と同形である、できるだけ多くの辺を持つグラフ H {\displaystyle H} ]。
一般グラフ上の最大共通エッジ部分グラフ問題は、部分グラフ同型写像の一般化であるため、NP完全である:グラフ H {\displaystyle H} G {\displaystyle G} の最大共通エッジ部分グラフが存在する場合に限り、別のグラフ G {\displaystyle G} の部分グラフと同形である]と H {\displaystyle H} のエッジ数は H {\displaystyle H} と同じです。最大共通エッジ部分グラフ問題に対する2つの入力 G {\displaystyle G} G {\displaystyle G’} が同じ頂点数を必要としない限り、問題はAPX-hardです。