頂点被覆問題

頂点被覆問題（ちょうてんひふくもんだい）は計算複雑性理論における問題の一つであり、 NP完全に属する問題の内のひとつ。

内容

頂点被覆問題はグラフ 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 の独立頂点集合が存在することは、同値だからである。