最小頂点被覆問題のソースを表示

'''最小頂点被覆問題'''（さいしょうちょうてんひふくもんだい）は、[[計算複雑性理論]]における[[NP困難]]な問題の一つ。

問題: [[グラフ理論|グラフ]] ''G''(''V'', ''E'') の各枝 ''e'' について端点のいずれか少なくとも一方が、''V''&prime; に含まれるような ''V'' の部分集合 ''V''&prime; のうち、|''V''&prime;| が最小になるものを求めよ

この問題の最適解を求めるのは、NP困難なため、決定性の[[多項式時間アルゴリズム]]は存在しないと考えられている。[[近似アルゴリズム]]に関して言えば、近似度2の[[貪欲アルゴリズム]]が存在することが知られているが、任意の &epsilon; &gt; 0 について、近似度 2 - &epsilon; の近似度を達成するアルゴリズムも存在しないだろうと考えられている。[[2005年]]現在の最良の近似度の下限は、<math>10\sqrt{5}-21 (>1.36)</math> である。

== 関連項目 ==
* [[頂点被覆]]
* [[最適化問題]]
* [[完全被覆問題]]
* [[最大独立集合問題]]

== 外部リンク ==
* [http://www.nada.kth.se/~viggo/wwwcompendium/node10.html MINIMUM VERTEX COVER]

{{DEFAULTSORT:さいしようちようてんひふくもんたい}}
[[Category:グラフ理論]]
[[Category:計算複雑性理論]]
[[Category:数学の問題]]
[[Category:数学に関する記事]]

[[en:Covering (graph theory)]]
[[es:Covering]]
[[he:כיסוי (תורת הגרפים)]]