NP完全問題
点カバー問題ともいう。グラフ G {\displaystyle G} と整数 k {\displaystyle k} が与えられる。このときGにサイズが高々 k {\displaystyle k} の点カバーが存在するか?という問題。この問題の最適化版(できるだけ少ない頂点数の点カバーを求める)は2-近似アルゴリズムを持ち、この近似比はP≠NPとユニークゲーム問題のNP困難性を仮定すれば最善である。