最大独立集合問題のソースを表示

'''最大独立集合問題'''（さいだいどくりつしゅうごうもんだい）は、[[グラフ理論]]において、与えられたグラフ G(V,E) に対して、頂点集合 V'⊆V のうち V' 内の頂点間に枝が存在しないようなもの（[[独立集合]]）で大きさが最大のものを求める問題。'''最大安定集合問題'''とも言う。この問題は、[[NP困難]]であることが知られている。

この問題は、[[補グラフ]]に対する[[最大クリーク問題]]と等価である。また、独立集合に含まれない頂点は[[頂点被覆]]をなし、逆も成り立つので、[[最小頂点被覆問題]]とも等価である。

[[近似アルゴリズム]]についても、基本的に最大クリーク問題と同じである。グラフの頂点数を n とするとき、[[近似度]] O(n / (log n)^2) が達成されている。また、P=[[NP]] が成り立たないとき、任意の ε>0 について、近似度 n^(1/2-ε) の近似アルゴリズムが存在しないことが示されている。NP=[[ZPP]]が成り立たない場合、近似度 n^(1-ε) の近似アルゴリズムが存在しないことも示されている。

グラフの最大[[次数 (グラフ理論)|次数]]を制限した場合は、以下の結果が知られている。
*次数2: [[多項式時間アルゴリズム]]が存在
*次数3: 1.2-近似アルゴリズムが存在。近似度の下限 1.0071
*次数4: 1.4-近似アルゴリズムが存在。近似度の下限 1.0136
*次数5: 1.6-近似アルゴリズムが存在。近似度の下限 1.0149

==関連項目==
*[[NP困難]]

==外部リンク==
*MAXIMUM INDEPENDENT SET [http://www.nada.kth.se/~viggo/wwwcompendium/node34.html]

{{デフォルトソート:さいたいとくりつしゆうこうもんたい}}
[[Category:グラフ理論]]
[[Category:数学の問題]]
[[Category:数学に関する記事]]

[[en:Independent set problem]]