頂点被覆問題

頂点被覆問題（ちょうてんひふくもんだい）は計算複雑性理論における問題の一つであり、NP完全に属する問題の内のひとつ。
内容.
頂点被覆問題はグラフ G(V,E)（Vは頂点、Eは辺）と k < |V| となる整数 k が与えられたとき、以下のような V の部分集合 V' を探索する問題である。
また|V'|の最小値を求める問題は最小頂点被覆問題といい、こちらはNP困難に属する問題になる。
頂点被覆問題は、独立集合問題と深く関係している。n 個の頂点のグラフに対して、大きさ k の頂点被覆が存在することと、大きさ n-k の独立頂点集合が存在することは、同値だからである。