最大独立集合問題

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動先: 案内検索

最大独立集合問題(さいだいどくりつしゅうごうもんだい)は、グラフ理論において、与えられたグラフ 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

関連項目[編集]

外部リンク[編集]

  • MAXIMUM INDEPENDENT SET [1]