Subgraph isomorphism problem とは

理論的計算科学では、サブグラフ同型性問題は、2つのグラフGとHが入力として与えられ、GがHと同型のサブグラフを含むかどうかを決定する計算タスクである。サブグラフ同型写像は、最大クリークグラフがハミルトニアンサイクルを含むかどうかをテストする問題であり、したがってNP完全である。しかし、部分グラフ同型写像の特定の他の場合は、多項式時間で解くことができる。
時には同じ名前の部分グラフマッチングも同じ問題に使用されます。この名前は、裸の決定問題とは対照的に、そのような部分グラフを見つけることに重点を置きます。