支配集合問題のソースを表示

'''支配集合問題'''（しはいしゅうごうもんだい）は、[[グラフ理論]]における有名な[[NP困難]]な問題の一つ。与えられた[[グラフ理論|グラフ]] ''G''(''V'', ''E'') の頂点集合 ''V''&prime; (&sube; ''V'') で、''V''&prime; に属さない全ての頂点 ''v'' について、''v'' の隣接頂点のいずれか一つが ''V''&prime; に属するような ''V''&prime; （支配集合）のうち、最小のものを求める問題。

この問題は、[[集合被覆問題]]に含まれるため、集合被覆問題への[[近似アルゴリズム]]を適用することで[[近似度]] 1 + log|''V''| の解を得ることができる。また、ある定数 ''c'' &gt; 0 について、''c'' log|''V''| 近似アルゴリズムが存在しないことも示されている。

しかし、[[平面グラフ]]に対しては、[[PTAS]] が存在することも知られている。

== 関連項目 ==
*[[NP完全]]
*[[アルゴリズム]]

== 外部リンク ==
*[http://www.nada.kth.se/~viggo/wwwcompendium/node11.html MINIMUM DOMINATING SET]

{{DEFAULTSORT:しはいしゆうこうもんたい}}
[[Category:グラフ理論]]
[[Category:数学に関する記事]]