独立集合（グラフ理論）

グラフ理論において、独立集合、安定集合、コクリーク、またはアンチクリークは、グラフ内のどの 2 つの頂点も隣接していない頂点の集合です。つまり、内の 2 つの頂点ごとに、その 2 つを接続する辺が存在しない頂点の集合です。同様に、グラフ内の各辺は 内に最大で 1 つの端点を持ちます。集合が独立であるためには、それがグラフの補集合内のクリークである必要があります。独立集合のサイズは、そこに含まれる頂点の数です。独立集合は「内部的に安定な集合」とも呼ばれ、「安定集合」はその短縮形です。^[1]${\displaystyle S}$${\displaystyle S}$${\displaystyle S}$

最大独立集合とは、他のどの独立集合の 適切な部分集合でもない独立集合です。

最大独立集合とは、与えられたグラフ に対して可能な最大サイズの独立集合のことである。このサイズはの独立数と呼ばれ、通常は と表記される。^[2]このような集合を見つける最適化問題は、最大独立集合問題と呼ばれる。これは強いNP 困難問題である。^[3]そのため、グラフ の最大独立集合を見つけるための効率的なアルゴリズムが存在する可能性は低い。 ${\displaystyle G}$${\displaystyle G}$${\displaystyle \alpha (G)}$

すべての最大独立集合は最大集合でもあるが、逆の含意は必ずしも成り立たない。

集合が独立であるためには、その集合がグラフの補集合内のクリークである必要があります。したがって、2 つの概念は相補的です。実際、大きなクリークのない十分に大きなグラフには大きな独立集合があり、これはラムゼー理論で研究されているテーマです。

集合が独立であるためには、その補集合が頂点被覆となる必要がある。^[4]したがって、最大の独立集合の大きさと最小の頂点被覆の大きさの合計は、グラフの頂点の数に等しい。 ${\displaystyle \alpha (G)}$${\displaystyle \beta (G)}$

グラフの頂点彩色は、その頂点集合を独立した部分集合に分割することに対応します。したがって、頂点彩色に必要な最小の色数、すなわち彩色数は、少なくとも の頂点数と独立数の商になります。 ${\displaystyle G}$ ${\displaystyle \chi (G)}$${\displaystyle G}$${\displaystyle \alpha (G)}$

孤立した頂点のない二部グラフでは、最大独立集合内の頂点の数は、最小辺被覆内の辺の数に等しくなります。これがケーニッヒの定理です。

別の独立集合の適切な部分集合ではない独立集合は最大と呼ばれます。このような集合は支配集合です。すべてのグラフには最大独立集合が最大で 3 ^{n /3 個含まれますが、 [5]}多くのグラフにはそれよりはるかに少ない数しかありません。n 頂点サイクルグラフの最大独立集合の数はペラン数で与えられ、 n頂点パスグラフの最大独立集合の数はパドバン数列で与えられます。^[6]したがって、両方の数は 1.324718... の累乗、つまり可塑性比 に比例します。

コンピュータサイエンスでは、独立集合に関連するいくつかの計算問題が研究されてきました。

• 最大独立集合問題では、入力は無向グラフであり、出力はグラフ内の最大独立集合です。最大独立集合が複数ある場合は、1 つだけ出力する必要があります。この問題は、「頂点パッキング」と呼ばれることもあります。
• 最大重み独立集合問題では、入力は頂点に重みがある無向グラフであり、出力は合計重みが最大である独立集合です。最大独立集合問題は、すべての重みが 1 である特殊なケースです。
• 最大独立集合リスト問題では、入力は無向グラフであり、出力はすべての最大独立集合のリストです。最大独立集合はすべての最大独立集合の中に含まれている必要があるため、最大独立集合リスト問題のアルゴリズムをサブルーチンとして使用して、最大独立集合問題を解くことができます。
• 独立集合決定問題では、入力は無向グラフと数値kであり、出力はブール値です。グラフにサイズkの独立集合が含まれている場合は true 、含まれていない場合は false です。

これらの問題のうち最初の 3 つはいずれも実際の応用において重要です。独立集合決定問題は重要ではありませんが、 NP 完全性の理論を独立集合に関連する問題に適用するためには必要です。

独立集合問題とクリーク問題は相補的です。つまり、 G内のクリークはGの補グラフ内の独立集合であり、その逆も同様です。したがって、多くの計算結果はどちらの問題にも同様に当てはまります。たとえば、クリーク問題に関連する結果には、次の帰結があります。

• 独立集合決定問題はNP 完全であるため、これを解決するための効率的なアルゴリズムは存在しないと考えられています。
• 最大独立集合問題はNP 困難であり、近似することも困難です。

任意のグラフにおける最大クリークと最大独立集合の間には密接な関係があるにもかかわらず、独立集合問題とクリーク問題は、グラフの特別なクラスに限定すると、大きく異なる可能性がある。例えば、スパースグラフ（任意のサブグラフの辺の数が最大でも頂点の数の定数倍であるグラフ）の場合、最大クリークのサイズは制限されており、正確に線形時間で見つけることができる。^[7]しかし、同じクラスのグラフ、またはより制限されたクラスの制限次数グラフの場合でも、最大独立集合を見つけることはMAXSNP 完全であり、これは、ある定数c（次数に依存）に対して、最適値のc倍以内の近似解を見つけることがNP 困難であることを意味する。^[8]

最大独立集合問題は NP 困難です。ただし、すべての頂点サブセットを調べて独立集合であるかどうかを確認する単純なブルートフォースアルゴリズムで得られるO( n ²  2 ⁿ ) 時間よりも効率的に解決できます。

2017年現在、多項式空間を使用してO(1.1996 ^{n )の時間で解くことができます。 [9]}最大次数3のグラフに制限すると、O(1.0836 ⁿ )の時間で解くことができます。^[10]

多くのグラフのクラスでは、最大重み独立集合は多項式時間で見つけることができます。有名な例としては、クローフリーグラフ^[11]、 P5_フリーグラフ^[12]、パーフェクトグラフ^[13]などがあります。弦グラフの場合、最大重み独立集合は線形時間で見つけることができます。^[14]

モジュラー分解は最大重み独立集合問題を解くための優れたツールであり、コグラフ上の線形時間アルゴリズムはその基本的な例です。もう1つの重要なツールは、Tarjanによって説明されたクリークセパレータです。^[15]

ケーニッヒの定理は、二部グラフでは二部マッチングアルゴリズムを使用して最大独立集合を多項式時間で見つけることができること を意味します。

一般に、最大独立集合問題は、多項式時間で定数因数に近似することはできません（P = NPでない限り）。実際、最大独立集合問題は一般に多項式因数に近似できる問題と同じくらい難しいことを意味しています。^[16] ただし、制限されたグラフクラスに対しては効率的な近似アルゴリズムが存在します。

平面グラフでは、最大独立集合は多項式時間で任意の近似比c  < 1の範囲内で近似することができる。同様の多項式時間近似スキームは、マイナーを取ることで閉じたグラフの族に存在する。^[17]

制限次数グラフでは、最大次数の固定値に対して近似率が一定である効果的な近似アルゴリズムが知られています。たとえば、各ステップでグラフ内の最小次数頂点を選択し、その近傍を削除することで最大独立集合を形成する貪欲アルゴリズムは、最大次数 Δ のグラフで近似率 (Δ+2)/3 を実現します。 ^[18]このようなインスタンスの近似困難性境界は、Berman & Karpinski (1999) で証明されました。実際、3 正則 3 辺彩色可能グラフ上の最大独立集合でさえAPX 完全です。^[19]

区間グラフは、ノードが 1 次元の区間 (時間区間など) であり、2 つの区間が交差する場合に限り、それらの区間の間にエッジが存在するグラフです。区間グラフの独立セットは、重複しない区間のセットにすぎません。区間グラフで最大の独立セットを見つける問題は、たとえばジョブ スケジューリングのコンテキストで研究されてきました。つまり、コンピューターで実行する必要があるジョブのセットが与えられた場合、互いに干渉せずに実行できるジョブの最大セットを見つけます。この問題は、最も早い期限優先スケジューリングを使用して、多項式時間で正確に解決できます。

幾何学的交差グラフは、ノードが幾何学的形状であり、交差する場合に限り 2 つの形状の間にエッジが存在するグラフです。幾何学的交差グラフの独立セットは、互いに素な (重なり合わない) 形状のセットです。幾何学的交差グラフで最大の独立セットを見つける問題は、たとえば、自動ラベル配置のコンテキストで研究されてきました。つまり、地図上の位置のセットが与えられた場合、これらの位置の近くにある互いに素な長方形ラベルの最大セットを見つけます。

交差グラフの最大独立集合を見つけることは依然として NP 完全ですが、一般的な最大独立集合問題よりも近似が容易です。最近の調査は Chan & Har-Peled (2012) の紹介に記載されています。

グラフのdクローはd +1 個の頂点のセットで、そのうちの 1 つ( 「中心」) は他のd個の頂点に接続されていますが、他の d 個の頂点は互いに接続されていません。dクローフリー グラフは、 dクロー サブグラフを持たないグラフです。空のセットから開始し、既存の頂点に隣接していない限り、任意の頂点を段階的に追加するアルゴリズムを考えてみましょう。d クローフリー グラフでは、追加された頂点ごとに最大独立セットから最大d -1 個の頂点が無効になります。したがって、この単純なアルゴリズムは、最大独立セットの ( d -1) 近似アルゴリズムを実現します。実際、はるかに優れた近似比を得ることができます。

• Neuwohner ^{[20]は、任意の定数ε>0に対して、} dクローフリーグラフの最大重み独立集合の( d /2-1/63,700,992+ε)近似値を求める多項式時間アルゴリズムを提示した。
• Cygan ^[21]は、任意のε>0に対して(d+ε)/3近似を達成する準多項式時間アルゴリズムを提示した。

最大独立集合を求める問題は、単純な並列貪欲アルゴリズムによって多項式時間で解くことができる。^{[22]すべての最大独立集合は、O(3 n /3} ) = O(1.4423 ⁿ )の時間で求めることができる。

数え上げ問題#ISは、無向グラフが与えられたとき、グラフに独立集合がいくつ含まれるかを問う問題である。この問題は扱いにくい。すなわち、最大次数3 のグラフ上ですでに♯P完全である。^{[23]さらに、} NP がRPと異なると仮定すると、最大次数 6 のグラフ上でも、ランダム化による完全多項式時間近似スキーム(FPRAS)が存在しないという意味で、この問題は扱いやすく近似できないことが知られている。 ^[24]ただし、最大次数が 5 の場合には、完全多項式時間近似スキーム (FPTAS) が存在する。^[25]二部グラフ上の独立集合を数える問題 #BISも、最大次数3 のグラフ上ですでに♯P完全である。^[26] #BIS が FPRAS を許容するかどうかは不明である。^[27]

最大独立集合を数える問題も研究されてきました。

最大独立集合とその補集合である最小頂点被覆問題は、多くの理論的問題の計算複雑性を証明することに関係している。^[28]これらは現実世界の最適化問題にも有用なモデルとして機能し、例えば最大独立集合は人工遺伝子システムを設計するための安定した遺伝子成分を発見するための有用なモデルである。^[29]

• 独立した辺の集合とは、どの 2 つも頂点を共有しない辺の集合です。これは通常、マッチングと呼ばれます。
• 頂点の色付けは、頂点集合を独立した集合に分割することです。

• Weisstein、Eric W.「最大独立頂点集合」。MathWorld。
• 最大クリーク、最大独立集合、最小頂点被覆、頂点彩色のベンチマークに挑戦 アーカイブ 2013-05-29 at the Wayback Machine
• 独立集合と頂点被覆、Hanan Ayad。