最小頂点被覆問題

最小頂点被覆問題（さいしょうちょうてんひふくもんだい）は、計算複雑性理論におけるNP困難な問題の一つ。問題: グラフ G(V, E) の各枝 e について端点のいずれか少なくとも一方が、V′ に含まれるような V の部分集合 V′ のうち、|V′| が最小になるものを求めよこの問題の最適解を求めるのは、NP困難なため、決定性の多項式時間アルゴリズムは存在しないと考えられている。