頂点被覆問題とはなんですか？

A. 頂点被覆問題とは、与えられたグラフの頂点のうち、全ての部分グラフが完全な被覆を持つかどうかを判定する問題です。つまり、全ての頂点が、与えられた部分グラフによって全て覆われているかどうかを判定します。この問題は、NP完全に属するため、計算複雑性理論における重要な問題の一つです。

参考URL:https://ja.wikipedia.org/wiki/%E9%A0%82%E7%82%B9%E8%A2%AB%E8%A6%86%E5%95%8F%E9%A1%8C