頂点被覆問題

頂点被覆問題はグラフ G(V,E)（Vは頂点、Eは辺）と k < |V| となる整数 k が与えられたとき、以下のような V の部分集合 V' を探索する問題である。

問題 グラフ G(V,E) の各枝 e について端点のいずれか少なくとも一方が、V' に含まれるような V の部分集合 V' のうち、|V'| = k となるものが存在するかを求めよ。

また|V'|の最小値を求める問題は最小頂点被覆問題といい、こちらはNP困難に属する問題になる。

頂点被覆問題は、独立集合問題と深く関係している。n 個の頂点のグラフに対して、大きさ k の頂点被覆が存在することと、大きさ n-k の独立頂点集合が存在することは、同値だからである。

• 頂点被覆
• NP完全問題
• 最小頂点被覆問題