独立集合（グラフ理論）
9つの青い頂点は、一般化ピーターセングラフGP(12,4)の最大独立集合を形成します。

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

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

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

すべての最大独立集合も最大ですが、逆の含意は必ずしも成り立ちません。

プロパティ

他のグラフパラメータとの関係

集合が独立であるためには、グラフの補集合におけるクリークが存在する必要がある。したがって、これら2つの概念は相補的である。実際、大きなクリークを持たない十分に大きなグラフは、大きな独立集合を持つ。これはラムゼー理論で探求されているテーマである。

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

グラフの頂点彩色は、その頂点集合を独立部分集合に分割することに対応する。したがって、頂点彩色に必要な最小の色数、すなわち彩色数は、グラフの頂点数と独立数との商以上である。 G{\displaystyle G}χ（G）{\displaystyle \chi (G)}G{\displaystyle G}α（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  2 n )の時間で解くよりも効率的に解くことができます。

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

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

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

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

近似アルゴリズム

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

平面グラフでは

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

有界次数グラフ

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

区間交差グラフ

区間グラフとは、ノードが1次元の区間（例えば時間区間）であり、2つの区間が交差する場合に限り、それらの区間の間に辺が存在するグラフです。区間グラフにおける独立集合とは、単に重複しない区間の集合です。区間グラフにおける最大独立集合を求める問題は、例えばジョブスケジューリングの文脈で研究されてきました。つまり、コンピュータ上で実行する必要があるジョブの集合が与えられたとき、互いに干渉することなく実行できるジョブの集合の最大集合を求める問題です。この問題は、最早期限優先スケジューリングを用いて、多項式時間で正確に解くことができます。

幾何学的交差グラフでは

幾何学的交差グラフとは、ノードが幾何学的図形であり、2つの図形が交差する場合に限り、2つの図形の間に辺が存在するグラフです。幾何学的交差グラフにおける独立集合とは、互いに素な（重なり合わない）図形の集合です。幾何学的交差グラフにおける最大独立集合を求める問題は、例えば自動ラベル配置の文脈で研究されてきました。地図上の位置の集合が与えられたとき、これらの位置の近傍にある互いに素な長方形ラベルの最大集合を求める問題です。

交差グラフにおける最大独立集合を求める問題は依然としてNP完全ですが、一般的な最大独立集合問題よりも近似が容易です。最近のサーベイは、Chan & Har-Peled (2012)の序文に記載されています。

d-claw-freeグラフ

グラフにおける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( 3n /3 )=O(1.4423n )の時間で求めることができる。

独立集合を数える

コンピュータサイエンスにおける未解決問題
二部グラフの独立集合の数を完全に多項式時間で近似するアルゴリズムはありますか?
コンピュータサイエンスにおけるさらなる未解決問題

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

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

アプリケーション

最大独立集合とその補集合である最小頂点被覆問題は、多くの理論的問題の計算複雑さを証明することに関係している。 [ 28 ]

参照

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

注記

  1. ^コルシュノフ（1974）
  2. ^ Godsil & Royle (2001)、3ページ。
  3. ^ゲイリーMR;ジョンソン、DS (1978-07-01)。」「「強力な」NP完全性の結果：動機、例、および影響」。ACMジャーナル。25（3）： 499-508。doi ：10.1145 / 322077.322090。ISSN 0004-5411。S2CID  18371269。 
  4. ^証明: 頂点の集合 V は独立集合です。グラフ内のすべての辺が V の要素の 1 つに隣接している場合、グラフ内のすべての辺が V にない要素の少なくとも 1 つに隣接している場合、V の補集合が頂点カバーである場合に限ります。
  5. ^ムーン＆モーザー（1965年）。
  6. ^ Füredi (1987) .
  7. ^千葉＆西関 (1985)。
  8. ^バーマン＆フジト（1995）。
  9. ^シャオ＆ナガモチ (2017)
  10. ^シャオ＆ナガモチ (2013)
  11. ^ミンティ (1980)、スビヒ (1980)、ナカムラ & タムラ (2001)、ファエンツァ、オリオロ & シュタウファー (2014)、ノビリ & サッサノ (2015)
  12. ^ロクシュタノフ、ヴァトシェル、ヴィレンジャー (2014)
  13. ^ Grötschel、Lovász、Schrijver (1993、第 9 章: グラフの安定集合)
  14. ^フランク（1976）
  15. ^タージャン（1985）
  16. ^ Bazgan, Cristina ; Escoffier, Bruno ; Paschos, Vangelis Th. (2005). 「標準近似クラスと微分近似クラスにおける完全性：ポリ(D)APX完全性と(D)PTAS完全性」理論計算機科学339 ( 2–3 ) : 272– 292. doi : 10.1016/j.tcs.2005.03.007 . S2CID 1418848 . 
  17. ^ベイカー (1994) ;グローエ (2003)。
  18. ^ Halldórsson & Radhakrishnan (1997)。
  19. ^ Chlebík, Miroslav; Chlebíková, Janka (2003). 「NP困難問題の小規模発生インスタンスに対する近似困難性」 .第5回アルゴリズムと計算量に関する国際会議議事録. コンピュータサイエンス講義ノート. 第2653巻. pp.  152– 164. doi : 10.1007/3-540-44849-7_21 . ISBN 978-3-540-40176-6。
  20. ^ Neuwohner, Meike (2021-06-07)、d-Clawフリーグラフにおける最大重み独立集合問題に対する改良近似アルゴリズム、arXiv : 2106.03545
  21. ^ Cygan, Marek (2013年10月). 「パス幅制限付き局所探索による3次元マッチングの近似値の改善」. 2013 IEEE 第54回コンピュータサイエンス基礎シンポジウム. pp.  509– 518. arXiv : 1304.1424 . doi : 10.1109/FOCS.2013.61 . ISBN 978-0-7695-5135-7. S2CID  14160646 .
  22. ^ルビー（1986） .
  23. ^ Dyer, Martin; Greenhill, Catherine (2000-04-01). 「独立集合のマルコフ連鎖について」 . Journal of Algorithms . 35 (1): 17– 49. doi : 10.1006/jagm.1999.1071 . ISSN 0196-6774 . 
  24. ^ Sly, Allan (2010). 「一意性閾値における計算遷移」. 2010 IEEE 第51回コンピュータサイエンス基礎シンポジウム. pp.  287– 296. arXiv : 1005.5584 . doi : 10.1109/FOCS.2010.34 . ISBN 978-1-4244-8525-3. S2CID  901126 .
  25. ^ Bezáková, Ivona; Galanis, Andreas; Goldberg, Leslie Ann; Guo, Heng; Štefankovič, Daniel (2019). 「強い空間混合が失敗した場合の相関減衰による近似」 . SIAM Journal on Computing . 48 (2): 279– 349. arXiv : 1510.09193 . doi : 10.1137/16M1083906 . ISSN 0097-5397 . S2CID 131975798 .  
  26. ^ Xia, Mingji; Zhang, Peng; Zhao, Wenbo (2007-09-24). 「3-正則平面グラフ上の計数問題の計算複雑性」 .理論計算機科学. 計算モデルの理論と応用. 384 (1): 111– 125. doi : 10.1016/j.tcs.2007.05.023 . ISSN 0304-3975 . Curticapean , Radu; Dell, Holger; Fomin, Fedor; Goldberg, Leslie Ann; Lapinskas, John (2019-10-01). "A Fixed-Parameter Perspective on #BIS" . Algorithmica . 81 (10): 3844– 3864. arXiv : 1702.05543 . doi : 10.1007/s00453-019-00606-4 . hdl : 1983/ecb5c34c-d6be-44ec-97ea-080f57c5e6af . ISSN 1432-0541 . S2CID 3626662 .  
  27. ^キャノン、サラ、パーキンス、ウィル (2020). チャウラ、シュチ (編).第14回ACM-SIAM離散アルゴリズムシンポジウム議事録. ペンシルベニア州フィラデルフィア: 産業応用数学協会. arXiv : 1906.01666 . doi : 10.1137/1.9781611975994.88 . ISBN 978-1-61197-599-4. S2CID  174799567 .
  28. ^スキエナ、スティーブン・S. (2012).アルゴリズム設計マニュアル. シュプリンガー. ISBN 978-1-84800-069-8. OCLC  820425142 .

参考文献

「 https://en.wikipedia.org/w/index.php?title=Independent_set_(graph_theory)&oldid=1335314589#Finding_maximum_independent_sets」より取得