最大独立集合

グラフ理論では、最大独立集合( MIS ) または最大安定集合は、他のどの独立集合の部分集合でもない独立集合です。言い換えると、独立集合プロパティに関して最大​​であるため、独立集合の外側に結合できる 頂点は存在しません。

たとえば、グラフP ₃（3 つの頂点a、b、cと 2 つの辺abとbc を持つパス）では、集合{ b }と{ a、c }は両方とも最大独立です。集合{ a }は独立していますが、より大きな独立集合{ a、c }のサブセットであるため、最大独立ではありません。この同じグラフでは、最大クリークは集合{ a、b }と{ b、c } です。

MIS はグラフ内の支配集合でもあり、独立したすべての支配集合は最大独立でなければならないため、MIS は独立支配集合とも呼ばれます。

グラフには、さまざまなサイズの MIS が多数存在することがあります。^[a]グラフの最大の MIS、または場合によっては同じ大きさの MIS が複数ある場合、これを最大独立集合と呼びます。すべての最大独立集合が同じサイズであるグラフを、よく覆われたグラフと呼びます。

「最大独立集合」という語句は、グラフ以外の数学的構造、特にベクトル空間やマトロイドにおける独立要素の最大部分集合を表す場合にも使用されます。

MIS には、特定のグラフ内で単一の MIS を見つけることと、特定のグラフ内のすべての MIS を一覧表示することという2 つのアルゴリズムの問​​題が関連しています。

グラフ に対して、独立集合 が最大独立集合であるとは、 に対して次のいずれかが真である場合である: ^[1]${\displaystyle G=(V,E)}$ ${\displaystyle S}$${\displaystyle v\in V}$

1. ${\displaystyle v\in S}$
2. ${\displaystyle N(v)\cap S\neq \emptyset }$ここで、は近傍を表す。${\displaystyle N(v)}$${\displaystyle v}$

上記は、頂点が独立集合に属するか、独立集合に属する少なくとも1つの隣接頂点を持つかのいずれかであると言い換えることができます。その結果、グラフのすべての辺には、に含まれない少なくとも1つの端点があります。ただし、グラフのすべての辺に、に含まれない少なくとも1つの端点がある、または1つの端点があるというわけではありません。${\displaystyle S}$${\displaystyle S}$

独立集合内の頂点の隣接頂点は、独立集合の定義により互いに分離されているため、独立集合 に含めることができないことに注意してください。${\displaystyle S}$${\displaystyle S}$

S があるグラフ内の最大独立集合である場合、それは相補グラフ内の最大クリークまたは最大完全サブグラフです。最大クリークは、完全サブグラフを誘導し、より大きな完全サブグラフの頂点のサブセットではない頂点の集合です。つまり、S内のすべての頂点のペアが辺で接続され、Sにないすべての頂点はS内の少なくとも 1 つの頂点への辺を欠いているような集合Sです。グラフには、さまざまなサイズの多くの最大クリークが存在する場合があります。これらの最大のクリークを見つけることが最大クリーク問題です。

一部の著者は、最大性をクリークの定義の一部として含め、最大クリークを単にクリークと呼んでいます。

最大独立集合の補集合、すなわち独立集合に属さない頂点の集合は、極小頂点被覆を形成する。すなわち、補集合は頂点被覆であり、各辺の少なくとも 1 つの端点を含む頂点の集合であり、被覆であるという性質を維持しながら頂点を削除することができないという意味で極小である。極小頂点被覆は、統計力学において、流体-固体状態遷移の数学的抽象化である剛球格子気体モデルに関連して研究されてきた。^[2]

すべての最大独立集合は支配集合、つまりグラフ内のすべての頂点がその集合に属するか、その集合に隣接する頂点の集合です。頂点の集合は、独立支配集合である場合にのみ、最大独立集合となります。

特定のグラフ族は、最大クリークまたは最大独立集合の観点からも特徴付けられる。例としては、最大クリーク既約グラフや遺伝的最大クリーク既約グラフなどがある。すべての最大クリークに他のどの最大クリークにも属さない辺がある場合、そのグラフは最大クリーク既約であると言われ、すべての誘導サブグラフに同じ特性が当てはまる場合、遺伝的最大クリーク既約であると言われる。 ^[3] 遺伝的最大クリーク既約グラフには、三角形のないグラフ、二部グラフ、区間グラフなどがある。

コグラフは、あらゆる最大クリークがあらゆる最大独立集合と交差し、すべての誘導サブグラフで同じ特性が成り立つグラフとして特徴付けることができます。

Moon & Moser (1965) は、 n頂点のグラフには最大3 ^{n /3 個}のクリークしかないことを示した。補足的に、 n頂点のグラフには最大 3 ^{n /3}個の独立集合しかない。最大独立集合がちょうど 3 ^{n /3 個}のグラフは簡単に構築できる。n /3 個の三角形グラフの非結合和をとるだけだ。このグラフの最大独立集合は、各三角形から 1 つの頂点を選ぶことで形成される。最大クリークがちょうど 3 n /3 個の補完グラフは、特別^なタイプのTurán グラフである。Moon と Moser の境界との関連から^、これらのグラフは Moon-Moser グラフとも呼ばれる。最大独立集合のサイズを制限すれば、より厳しい境界が可能になる。n頂点グラフのサイズkの最大独立集合の数は、最大で

${\displaystyle \lfloor n/k\rfloor ^{k-(n{\bmod {k}})}\lfloor n/k+1\rfloor ^{n{\bmod {k}}}.}$

この境界を満たすグラフは再びトゥラングラフである。^[4]

ただし、グラフの特定の族では、最大独立集合または最大クリークの数に関して、はるかに厳しい制限がある場合があります。グラフの族内のすべてのn頂点グラフが O( n ) 個のエッジを持ち、族内のグラフのすべてのサブグラフも族に属している場合、族内の各グラフは最大で O( n ) 個の最大クリークを持つことができ、それらのサイズはすべて O(1) です。^[5]たとえば、これらの条件は平面グラフに当てはまります。すべてのn頂点平面グラフは最大で 3 n − 6 個のエッジを持ち、平面グラフのサブグラフは常に平面であるため、各平面グラフには O( n ) 個の最大クリーク（サイズは最大で 4） があることになります。区間グラフと弦グラフも、常にスパースグラフであるとは限りませんが、最大でn個のクリークを持ちます。

n頂点サイクルグラフにおける最大独立集合の数はペラン数で与えられ、 n頂点パスグラフにおける最大独立集合の数はパドバン数列で与えられる。^{[6]したがって、両方の数は}塑性比1.324718の累乗に比例する。

グラフ G(V,E) が与えられた場合、次のアルゴリズムを使用して単一の MIS を簡単に見つけることができます。

1. I を空のセットに初期化します。
2. V が空ではない間:
   • ノードv∈Vを選択します。
   • 集合Iにvを追加します。
   • V からノード v とそのすべての隣接ノードを削除します。
3. I を返します。

次のアルゴリズムは、O(log n )の時間でMISを見つけます。^{[1] [7] [8]}

1. I を空のセットに初期化します。
2. V が空ではない間:
   • 各頂点 v を確率 1/(2d(v)) で独立に選択することにより、頂点のランダムな集合 S ⊆ V を選択します。ここで、d は v の次数 (v に隣接する頂点の数) です。
   • E のすべての辺について、その両方の端点がランダム セット S 内にある場合、次数が低い (つまり、近傍が少ない) 端点を S から削除します。頂点名に辞書式順序を使用するなどして、同点を任意に決定します。
   • 集合SをIに加えます。
   • V から集合 S と S 内のノードのすべての隣接ノードを削除します。
3. I を返します。

分析: 各ノード v について、その近傍を下位近傍(次数が v の次数より低い) と上位近傍 (次数が v の次数より高い) に分割し、アルゴリズムに従って同点の場合は分割します。

ノード vの近傍の 2/3 以上が高位近傍である場合、そのノードは不良であると呼びます。エッジの両方のエンドポイントが不良である場合、そのエッジは不良であると呼びます。それ以外の場合は、エッジは良好です。

• すべてのエッジの少なくとも半分は常に良好です。証明: 各エッジをより高い次数のノードに向けることで (同点の場合は任意に切断)、G の有向バージョンを構築します。したがって、すべての不良ノードについて、出力エッジの数は、入力エッジの数の 2 倍以上になります。したがって、ノード v に入るすべての不良エッジは、ノード v から出る 2 つのエッジの個別のセットに一致できます。したがって、エッジの合計数は、不良エッジの数の少なくとも 2 倍になります。
• すべての良いノード u について、u の隣接ノードが S に選択される確率は、少なくとも一定の正の定数です。証明: u の隣接ノードが S に選択されない確率は、最大でも u の下位隣接ノードがいずれも選択されない確率です。各下位隣接ノード v について、選択されない確率は (1-1/2d(v)) で、最大でも (1-1/2d(u)) です (d(u)>d(v) であるため)。u は良いノードなので、そのような隣接ノードの数は少なくとも d(u)/3 です。したがって、下位隣接ノードが選択されない確率は最大でも 1-exp(-1/6) です。
• S に選択されるすべてのノード u について、u が S から削除される確率は最大で 1/2 です。証明: この確率は、u の上位隣接ノードが S に選択される確率に最大で相当します。各上位隣接ノード v について、それが選択される確率は最大で 1/2d(v) であり、これは最大で 1/2d(u) です (d(v)>d(u) であるため)。和集合により、上位隣接ノードが選択されない確率は最大で d(u)/2d(u) = 1/2 です。
• したがって、すべての良いノード u について、u の隣接ノードが S に選択され、S に残る確率は、一定の正の定数です。したがって、各ステップで u が削除される確率は、少なくとも正の定数です。
• したがって、すべての良好なエッジ e について、各ステップで e が削除される確率は少なくとも正の定数です。したがって、良好なエッジの数は各ステップで少なくとも定数倍減少します。
• 少なくとも半分のエッジは良好なので、エッジの合計数も各ステップごとに一定の割合で減少します。
• したがって、ステップ数は O(log m ) です。ここで、mはエッジの数です。これは によって制限されます。${\displaystyle O(\log(n))}$

平均ステップ数が である最悪のグラフは、それぞれ 2 つのノードを持つn /2 個の連結コンポーネントで構成されるグラフです。すべてのノードの次数は 1 なので、各ノードは 1/2 の確率で選択され、コンポーネント内の両方のノードが選択されない確率は 1/4 です。したがって、ノードの数はステップごとに 4 分の 1 に減少し、予想されるステップ数は です。 ${\displaystyle \Theta (\log(n))}$${\displaystyle \log_{4}(n)}$

次のアルゴリズムは、各接続コンポーネントに少なくとも1つの新しいノードが常に追加される点で、前のアルゴリズムよりも優れています。^{[9] [8]}

1. I を空のセットに初期化します。
2. V が空でない場合、各ノード v は次の処理を実行します。
   • [0,1]内の乱数r(v)を選択し、それを隣接する乱数に送信します。
   • r(v) が v のすべての隣接要素の数よりも小さい場合、v は自身を I に挿入し、自身を V から削除し、そのことを隣接要素に通知します。
   • v は、その近隣の 1 つが I に入ったことを聞いた場合、V から自身を削除します。
3. I を返します。

各ステップで、各接続コンポーネント内の最小番号のノードが常に I に入るため、常に何らかの進行があることに注意してください。特に、前のアルゴリズムの最悪のケース (それぞれ 2 つのノードを持つn /2 個の接続コンポーネント) では、MIS が 1 つのステップで見つかります。

分析：

• ノードは、削除される可能性が少なくともあります。証明: ノード のペアを接続する各エッジを、と からの 2 つの有向エッジに置き換えます。 が2 倍の大きさになることに注意してください。 のすべての有向エッジ のペアについて、2 つのイベントを定義します。と は、それぞれ、を先制的に削除し、 を先制的に削除します。イベントは、 およびのときに発生します。ここで、 はの隣接ノードであり、 は の隣接ノードです。各ノードには、同じ [0, 1] の範囲の乱数が与えられることを思い出してください。 が互いに素な 2 つのノードを持つ簡単な例では、それぞれが最小になる確率があります。 が互いに素な 3 つのノードである場合、それぞれが 最小になる確率があります。 の場合、 の隣接ノードが の隣接ノードでもある可能性があるため、 が最小になる確率が少なくとも あり、ノードが二重にカウントされます。同じロジックを使用すると、イベントも削除される確率が少なくともあります 。${\displaystyle v}$${\displaystyle {\frac {1}{d(v)+d(w)}}}$${\displaystyle (v,w)}$${\displaystyle (v,w)}$${\displaystyle (w,v)}$${\displaystyle |E|}$${\displaystyle (v,w)}$${\displaystyle (v\rightarrow w)}$${\displaystyle (w\rightarrow v)}$${\displaystyle v}$${\displaystyle w}$${\displaystyle w}$${\displaystyle v}$${\displaystyle (v\rightarrow w)}$${\displaystyle r(v)<r(w)}$${\displaystyle r(v)<r(x)}$${\displaystyle w}$${\displaystyle v}$${\displaystyle x}$${\displaystyle w}$${\displaystyle {\frac {1}{2}}}$${\displaystyle {\frac {1}{3}}}$${\displaystyle v}$${\displaystyle {\frac {1}{d(v)+d(w)}}}$${\displaystyle v}$${\displaystyle w}$${\displaystyle (w\rightarrow v)}$${\displaystyle {\frac {1}{d(w)+d(v)}}}$
• イベントと が発生すると、それぞれ と の有向出力エッジが削除されます。証明: イベント で が削除されると、すべての隣接ノードも削除されます。削除される からの出力有向エッジの数はです。同じロジックで、 は有向出力エッジを削除します。${\displaystyle (v\rightarrow w)}$${\displaystyle (w\rightarrow v)}$${\displaystyle d(w)}$${\displaystyle d(v)}$${\displaystyle (v\rightarrow w)}$${\displaystyle v}$${\displaystyle w}$${\displaystyle w}$${\displaystyle d(w)}$${\displaystyle (w\rightarrow v)}$${\displaystyle d(v)}$
• ステップ 2 の各反復では、期待どおりに、半分のエッジが削除されます。証明: イベントが 発生した場合、 のすべての隣接エッジが削除されます。したがって、このイベントにより削除されるエッジの期待数は少なくとも です。逆のイベント についても同じことが言えます。つまり、削除されるエッジの期待数は少なくとも です。したがって、すべての無向エッジ について、これらのノードの 1 つが最小値を持つために削除されるエッジの期待数は です。すべてのエッジ を合計すると、ステップごとに削除されるエッジの期待数が得られますが、各エッジは 2 回 (方向ごとに 1 回) カウントされるため、 ステップごとに削除されるエッジの期待数が与えられます。${\displaystyle (v\rightarrow w)}$${\displaystyle w}$${\displaystyle {\frac {d(w)}{d(v)+d(w)}}}$${\displaystyle (w\rightarrow v)}$${\displaystyle {\frac {d(v)}{d(w)+d(v)}}}$${\displaystyle (w,v)}$${\displaystyle {\frac {d(w)+d(v)}{d(w)+d(v)}}=1}$${\displaystyle \sum _{{v,w}\in E}1=|E|}$${\displaystyle |E|}$${\displaystyle {\frac {|E|}{2}}}$
• したがって、アルゴリズムの期待実行時間は、となる。^[8]${\displaystyle 3\log _{4/3}(m)+1}$${\displaystyle O(\log(n))}$

各ステップでランダム化を行う代わりに、ノードのランダムな順序を固定することで、アルゴリズムの開始時に一度だけランダム化することも可能です。この固定された順序を考えると、次の並列アルゴリズムは#Sequentialアルゴリズムとまったく同じMISを実現します（つまり、結果は決定論的です）。^[10]

1. I を空のセットに初期化します。
2. V が空ではない間:
   • W を、V 内の、先行する隣接頂点を持たない頂点の集合とする（固定順序に基づく）。
   • W を I に追加します。
   • V からセット W 内のノードとそのすべての隣接ノードを削除します。
3. I を返します。

完全に順次的なアルゴリズムと完全に並列なアルゴリズムの間には、部分的に順次的で部分的に並列なアルゴリズムの連続体があります。ノードの順序が固定され、係数 δ∈(0,1] が与えられている場合、次のアルゴリズムは同じ MIS を返します。

1. I を空のセットに初期化します。
2. V が空ではない間:
   • 係数δ∈(0,1]を選択します。
   • 固定順序で最初に位置するδn個のノードの集合をPとする。
   • 完全並列アルゴリズムを使用して、W を P 上の MIS とします。
   • W を I に追加します。
   • V からプレフィックス P 内のすべてのノードと、セット W 内のすべてのノードの隣接ノードを削除します。
3. I を返します。

δ=1/ nに設定すると完全に順次的なアルゴリズムが得られ、δ=1 に設定すると完全に並列なアルゴリズムが得られます。

分析: 部分並列アルゴリズムのパラメータ δ を適切に選択すると、完全並列アルゴリズムの呼び出し回数が最大で log(n) 回で終了し、各呼び出しのステップ数が最大で log(n) になることを保証できます。したがって、部分並列アルゴリズムの合計実行時間は です。したがって、完全並列アルゴリズムの実行時間も最大で です。主な証明手順は次のとおりです。 ${\displaystyle O(\log ^{2}(n))}$${\displaystyle O(\log ^{2}(n))}$

• ステップiで （ Dはグラフ内のノードの最大次数）を選択した場合、ステップiの後に残っているすべてのノードの次数は最大で になります。したがって、log( D ) ステップの後、残っているすべてのノードの次数は 0 になり（D < nなので）、1 つのステップで削除できます。${\displaystyle \delta =2^{i}\log {(n)}/D}$${\displaystyle D/2^{i}}$
• どのステップでも、各ノードの次数が最大でdであり、 (任意の定数Cに対して)を選択した場合、固定順序によって決定される有向グラフ内の最長パスWHP の長さは になります。したがって、完全並列アルゴリズムは最大でステップかかります (最長パスは、そのアルゴリズムのステップ数に対する最悪のケースの境界であるため)。${\displaystyle \delta =C\log {(n)}/d}$${\displaystyle O(\log(n))}$${\displaystyle O(\log(n))}$
• これら 2 つの事実を組み合わせると、 を選択した場合、部分並列アルゴリズムの実行時間は であることがわかります。${\displaystyle \delta =2^{i}\log {(n)}/D}$${\displaystyle O(\log(D)\log(n))=O(\log ^{2}(n))}$

グラフ内のすべての最大独立集合または最大クリークをリストするアルゴリズムは、多くの NP 完全グラフ問題を解くためのサブルーチンとして使用できます。最も明らかなのは、最大独立集合問題、最大クリーク問題、および最小独立支配問題に対する解はすべて最大独立集合または最大クリークでなければならないことであり、すべての最大独立集合または最大クリークをリストし、最大または最小のサイズのものを保持するアルゴリズムによって見つけることができます。同様に、最小頂点カバーは、最大独立集合の 1 つの補集合として見つけることができます。Lawler (1976) は、最大独立集合のリストを使用してグラフの 3 色を見つけることもできることを観察しました。つまり、グラフが 3 色にできるのは、その最大独立集合の 1 つの補集合が2 部である場合のみです。彼はこのアプローチを3色化だけでなく、より一般的なグラフ色化アルゴリズムの一部として使用し、グラフ色化に対する同様のアプローチはそれ以来他の著者によって改良されてきました。^[11]他のより複雑な問題も、特定のタイプのクリークまたは独立集合を見つけることとしてモデル化できます。これが、すべての最大独立集合（または同等に、すべての最大クリーク）を効率的にリストするというアルゴリズムの問​​題の動機となります。

ムーンとモーザーによる最大独立集合の数の3 ^{n /3 の}上限の証明を、そのような集合をすべて O(3 ^{n /3} ) の時間でリストするアルゴリズムに変換するのは簡単です。^[12]最大独立集合の数が最も多いグラフの場合、このアルゴリズムは出力集合ごとに一定の時間がかかります。ただし、この時間制限のあるアルゴリズムは、独立集合の数が少ないグラフでは非常に非効率的になる可能性があります。このため、多くの研究者が出力集合ごとに多項式時間ですべての最大独立集合をリストするアルゴリズムを研究してきました。^{[13]最大独立集合あたりの時間は、密なグラフでは}行列乗算に比例しますが、さまざまなクラスの疎なグラフではそれよりも速くなります。^[14]

最大独立集合に関する計数問題は計算複雑性理論で研究されてきた。この問題は、無向グラフが与えられたとき、それに含まれる最大独立集合の個数を問うものである。この問題は、入力が二部グラフに制限されているときでも、 #P困難である。^[15]

しかし、この問題は特定のグラフのクラスでは扱いやすく、例えばコグラフでは扱いやすい。^[16]

最大独立集合問題は、辞書式最大独立集合がP完全であることが証明されたため、当初は並列化が簡単ではないと考えられていました。しかし、最大集合パッキング問題または最大マッチング問題からの還元、あるいは2-充足可能性問題からの還元によって、決定論的な並列ソリューションが得られることが示されました。^{[17] [18]}通常、与えられたアルゴリズムの構造は他の並列グラフアルゴリズムに従います。つまり、それらはグラフを、同一のアルゴリズムを実行することで並列に解決可能な、より小さなローカル問題に分割します。 ${\displaystyle NC^{1}}$${\displaystyle NC^{2}}$

最大独立集合問題に関する初期の研究はPRAM モデルから始まり、その後、コンピュータ クラスター上の分散アルゴリズムの結果を生み出すまでに拡大しました。分散並列アルゴリズムの設計に関する多くの課題は、最大独立集合問題にも当てはまります。特に、グラフを細分化して独立集合をマージするための効率的な実行時間とデータ通信を最適化するアルゴリズムを見つけることが課題です。

1984 年に Karp らは、最大独立集合に対する PRAM 上の決定論的並列解が のNick のクラス複雑度動物園に属することを示した。^[19]つまり、彼らのアルゴリズムは （ は頂点集合のサイズ）を使用して の最大独立集合を求める。同じ論文では、プロセッサ を使用しての実行時間でランダム化並列解も提供された。その後まもなく、Luby と Alon らは独立にこの結果を改良し、最大独立集合問題を（ はグラフの辺の数）プロセッサを使用した実行時間での領域に持ち込んだ。 ^{[18] [7] [20]}彼らは、彼らのアルゴリズムが にあることを示すために、プロセッサを使用するが、プロセッサを追加することでランダム化を解除できるランダム化アルゴリズムを最初に提示した。今日、最大独立集合問題が にあるかどうかは未解決の問題である。 ${\displaystyle NC_{4}}$${\displaystyle O(\log^{4}n)}$${\displaystyle O((n/\log n)^{3})}$${\displaystyle n}$${\displaystyle O(\log^{4}n)}$${\displaystyle O(n^{2})}$${\displaystyle NC_{2}}$${\displaystyle O(\log^{2}n)}$${\displaystyle O(mn^{2})}$${\displaystyle m}$${\displaystyle NC_{2}}$${\displaystyle O(m)}$${\displaystyle O(n^{2})}$${\displaystyle NC_{1}}$

分散最大独立集合アルゴリズムは、PRAMモデルのアルゴリズムの影響を強く受けています。 LubyとAlonらによるオリジナルの研究は、いくつかの分散アルゴリズムにつながりました。^{[21] [22] [23] [20]}ビットの交換に関しては、これらのアルゴリズムはビットのラウンドごとにメッセージサイズの下限があり、グラフの追加の特性を必要とします。たとえば、グラフのサイズを知る必要があるか、特定の頂点の隣接頂点の最大次数を照会することができます。 2010年に、Métivierらはラウンドごとに必要なメッセージサイズを に削減しました。これは最適であり、追加のグラフ知識の必要性を排除しました。^[24]${\displaystyle O(\log n)}$${\displaystyle O(1)}$