Graph isomorphism problem とは

グラフ同型問題は、2つの有限グラフが同形であるかどうかを決定する計算上の問題である。
この問題は、多項式時間で解くこともNP完全でないことも知られておらず、したがって計算複雑度クラスNP中間である可能性がある。グラフ同型性問題は、クラスNPの低階層にあり、多項式時間階層がその第2レベルに崩壊しない限り、NP完全ではないことを意味することが知られている。同時に、多くの特殊クラスのグラフの同型写像は多項式時間で解くことができ、実際にはグラフ同型写像はしばしば効率的に解くことができる。
この問題は、所与のグラフGが別の所与のグラフHと同形であり、NP完全であることが知られている部分グラフを含むか否かを尋ねる部分グラフ同型問題の特別な場合である。対称グループよりも非アーベルの隠れサブグループ問題の特殊なケースであることも知られています。
画像認識の分野では、正確なグラフマッチングとして知られている。