マックスDDBS

最大次数と直径が制限された部分グラフ問題 (MaxDDBS)は、グラフ理論における問題です。

接続されたホストグラフが与えられた場合${\displaystyle G}$次数の上限${\displaystyle \Delta }$直径の上限値${\displaystyle D}$最大のサブグラフを探します${\displaystyle S}$の${\displaystyle G}$最大次数は${\displaystyle \Delta }$直径最大${\displaystyle D}$[ ^{1 ]​}

この問題は、十分大きな完全グラフをホストグラフとして扱うことで次数直径問題を特殊なケースとして含んでいるため、次数直径部分グラフ問題とも呼ばれます。次数直径問題の自然な一般化であるにもかかわらず、MaxDDBS の研究が始まったのは 2011 年になってからであり、次数直径問題の研究は 1960 年代から活発に行われています。^{[ 1 ]}

また、この問題には重み付きバージョン（MaxWDDBS）もあり、エッジには正の整数値の重みが付けられ、直径は最短経路に沿った重みの合計として測定されます。^{[ 1 ]}

計算複雑性に関して言えば、この問題はNP困難であり、APXには該当しません（つまり、多項式時間で定数係数の範囲内で近似することはできません）。^{[ 2 ]}制約を1つ（次数または直径のいずれか）に限定した場合でも、問題はNP困難のままです。^{[ 1 ]}

最大次数制限部分グラフ問題は、部分グラフが連結でなければならない場合、NP困難であるが、最大直径制限部分グラフは最大クリーク問題になる。${\displaystyle D=1}$これは、カープの21のNP完全問題の1つでした。^{[ 1 ]}

最大次数を持つ任意のグラフの次数${\displaystyle \Delta }$直径${\displaystyle D}$ムーア限界を超えることはできない：^{[ 1 ]}

${\displaystyle M_{\Delta ,D}=1+\Delta +\Delta (\Delta -1)+\cdots +\Delta (\Delta -1)^{D-1}}$

この境界は、MaxDDBS の理論的な上限としても機能します。${\displaystyle N_{\Delta ,D}}$最大次数を持つ最大のグラフのオーダー${\displaystyle \Delta }$直径${\displaystyle D}$すると、どんな解でも${\displaystyle S}$MaxDDBSの${\displaystyle n}$頂点:

${\displaystyle n\leq N_{\Delta ,D}\leq M_{\Delta ,D}}$

MaxDDBSには多様な実用的な用途があります: ^{[ 1 ]}

• 並列分散コンピューティング：並列処理において、通信時間は非常に重要です。並列アーキテクチャ内で次数と直径が限定されたサブネットワークを特定することで、効率的な計算が可能になります。
• ネットワークセキュリティとボットネット：ボットネット分析において、攻撃者は検出を回避しつつ被害を最大化するために、特定の次数と直径の制約を持つサブネットワークを選択する場合があります。MaxDDBSを理解することで、攻撃ネットワークのパラメータを予測し、防御策を策定するのに役立ちます。
• 生物学的ネットワーク：この問題は、タンパク質相互作用ネットワークに適用され、ネットワークの中核を特定するために用いられてきた。次数と直径の両方を制限することで（直径のみを制限するのではなく）、より豊かな相互作用パターンを明らかにすることができる。

MaxWDDBS に対して、最悪ケース近似比が以下の貪欲ヒューリスティックアルゴリズムが提案されている。${\displaystyle {\frac {\min(n,N_{\Delta ,D})}{\Delta +1}}}$、 どこ${\displaystyle n}$はホストグラフの頂点の数です。^{[ 1 ]}アルゴリズムは、${\displaystyle \Delta }$-スターとサブグラフは、次数制約を維持しながらこれ以上エッジを追加できなくなるまで、生きている頂点に接続するエッジを追加して成長します。

直径制限付きバリアントのみの場合、近似比を持つアルゴリズムが存在する。${\displaystyle O(n^{1/2})}$[ ^{1 ]​}

さまざまなホストグラフに関する実験的研究では、貪欲アルゴリズムは、反プリズムグラフやランダムグラフ（ワッツ・ストロガッツモデルやバラバシ・アルバートモデル）などにおいて、理論上の最悪の場合の限界が示唆するよりもはるかに優れたパフォーマンスを発揮することが多いことが示されている。^{[ 1 ]}

この問題は、さまざまなホストグラフファミリーについて研究されており、メッシュネットワーク、ハイパーキューブ、ハニカムネットワーク、三角形ネットワーク、バタフライネットワーク、ベネシュネットワーク、酸化物ネットワークの境界が確立されています。^{[ 3 ]}

組み合わせ論WikiのMaxDDBSページ