密なサブグラフ

グラフ理論とコンピュータサイエンスでは、密なサブグラフとは、頂点ごとに多数の辺を持つサブグラフのことです。これは次のように形式化されます。G = ( V 、E )を無向グラフとし、S = ( V _S、E _S )をGのサブグラフとします。この場合、Sの密度は次のように定義されます。

${\displaystyle d(S)={|E_{S}| \over |V_{S}|}}$

グラフの最大密度サブグラフの密度は、サブグラフ密度と呼ばれることもあります。最大密度のサブグラフは、グラフの平均次数が最大であるサブグラフとも見ることができます。

サブグラフ密度は、関連する概念である樹状性およびグラフの退化に漸近します。

最も密なサブグラフ問題とは、最大密度のサブグラフを見つける問題です。1984 年に、Andrew V. Goldberg は、最大フロー法を使用して最大密度サブグラフを見つける多項式時間アルゴリズムを開発しました。これは、1989 年に Gallo、Grigoriadis、Tarjan によって改良され、 O ( nm log( n ² / m ))時間で実行できるようになりました^[1]。最適解を見つけるための簡単な LP は、2000 年に Charikar によって示されました^[2]。

最密部分グラフ問題を解くための厳密なアルゴリズムの多くは、現実世界のデータでは非実用的であるため^[3] 、最密部分グラフ問題の近似アルゴリズムの研究につながっています。最密部分グラフを見つけるための簡単な近似は、1996 年に朝日朗、岩間、玉木、徳山によって最密部分グラフ問題の近似アルゴリズムとして最初に提案された剥離手順に基づいて、2000 年に Charikar によって与えられました。^[4]このアルゴリズムでは、次数が最も低い頂点が繰り返し削除され、頂点の順序が作成されます。ここで、 は削除されるグラフ内の 番目の頂点です。アルゴリズムによって返される部分グラフは、最も高い密度を持つセットによって誘導されるグラフです。Charikar は、彼が提供した厳密なアルゴリズムの LP の双対を使用して、この手順が線形時間で実行され、少なくとも最適密度の 50% の部分グラフを生成することを証明しました。^[2] 50%は厳しい上限ではあるが、実際にはこの貪欲な剥離手順により、現実世界のグラフ上で最適密度の約80%が得られる。^[3]${\textstyle {\frac {1}{2}}}$${\displaystyle k}$${\displaystyle v_{1},v_{2},\dots ,v_{n}}$${\displaystyle v_{i}}$${\displaystyle i}$${\displaystyle S_{i}=\{v_{i},v_{i+1},\dots ,v_{n}\}}$

2020年に、Boobらは、剥離手順を複数回繰り返すことで最適なサブグラフに近づくことを目的とした反復剥離アルゴリズムを提示した。^[3]現在の次数に基づいて頂点を削除する代わりに、以前の反復のデータに基づいて各頂点に負荷が割り当てられ、頂点は負荷に基づいて剥離される。2022年に、Chekuri、Quanrud、およびTorresは、この手順がアルゴリズムの反復後に最も密なサブグラフ問題の近似値に収束することを証明した。ここで、は最適な密度、はグラフの最大次数である。^{[5]彼らはまた、同様のアルゴリズムを使用して最も密な}ハイパーグラフを見つけることができることを示しました。 ${\displaystyle (1-\epsilon )}$${\textstyle O({\frac {\Delta \log n}{\lambda ^{*}\epsilon ^{2}}})}$${\textstyle \lambda ^{*}}$${\displaystyle \Delta }$

最密部分グラフ問題には多くのバリエーションがある。その 1 つが最密k部分グラフ問題であり、その目的はちょうどk個の頂点の最大密度部分グラフを見つけることである。この問題はクリーク問題を一般化したものであり、したがって一般グラフではNP 困難である。任意の に対しての比率以内で最密k部分グラフを近似する多項式アルゴリズムが存在するが^[6]、指数時間仮説が偽でない限り多項式時間で -近似することはできない。^[7]というより弱い仮定の下では、この問題に対するPTAS は存在しない。^[8]${\displaystyle n^{1/4\,+\,\epsilon }}$${\displaystyle \epsilon >0}$${\displaystyle n^{1/\!\operatorname {polyloglog} n}}$${\displaystyle {\mathsf {NP}}\nsubseteq \bigcap _{\epsilon >0}{\mathsf {BPTIME}}(2^{n^{\epsilon }})}$

この問題は、二部グラフや弦グラフではNP困難のままであるが、木や分割グラフでは多項式問題である。^[9] （適切な）区間グラフや平面グラフでは、問題がNP困難か多項式問題かは不明である。しかし、部分グラフが連結されていることが求められる問題のバリエーションは、平面グラフではNP困難である。^[10]

最大密度問題の目的は、最大頂点数の最大密度サブグラフを見つけることです。アンダーセンとシェラピラは、この問題に -近似が存在する場合、それが最密サブグラフ問題の -近似につながることを示しました。^{[11]その後、これは}クラーとサハによって改良され、最大密度サブグラフの -近似は最密サブグラフ問題の -近似を意味することが示されました。^[12]${\displaystyle k}$${\displaystyle k}$${\displaystyle \alpha }$${\displaystyle \Theta (\alpha ^{2})}$${\displaystyle k}$${\displaystyle \alpha }$${\displaystyle k}$${\displaystyle 4\alpha }$${\displaystyle k}$

最小最密問題は、最大最密部分グラフ問題と同様に定義される。この問題はNP完全であるが^[12]、多項式時間で2近似することができる。^[13]さらに、この近似アルゴリズムが本質的に最良であるという証拠もある。小集合拡張仮説（ユニークゲーム予想に密接に関連する計算複雑性の仮定）を仮定すると、すべての定数に対して問題を係数以内に近似することはNP困難である。^[14]${\displaystyle k}$${\displaystyle k}$${\displaystyle (2-\epsilon )}$${\displaystyle \epsilon >0}$

Charalampos Tsourakakis は、- クリークの最密部分グラフ問題を導入しました。この最密部分グラフ問題のバリエーションは、によって誘導される- クリークの集合である、誘導されるクリークの平均数を最大化することを目的としています。最密部分グラフ問題は、 の特殊なケースとして得られることに注意してください。この一般化により、大規模な実世界のネットワークから大規模な近似クリークを抽出するための、経験的に成功した多項時間アプローチが提供されます。 ${\displaystyle k}$${\displaystyle k}$${\displaystyle d_{k}(S)={|C_{k}(S)| \over |V_{S}|}}$${\displaystyle C_{k}(S)}$${\displaystyle k}$${\displaystyle S}$${\displaystyle k=2}$

Qin らは、グラフ内の上位k個の局所的に最も密なサブグラフを発見する問題を提示しました。これらのサブグラフはそれぞれ、グラフ内のローカル領域で最高の密度を実現します。つまり、同じかそれ以上の密度を持つスーパーグラフに含まれず、密度がローカルで最も密なサブグラフの残りの部分と緩く接続されているサブグラフも含みません。最も密なサブグラフ問題は、の特殊なケースとして得られることに注意してください。グラフ内の局所的に最も密なサブグラフの集合は、多項式時間で計算できます。 ${\displaystyle k=1}$