問題

動的プログラミングを使用してツリー分解の最大独立セット問題を理解しようとしています。しかし、私は提案されたアルゴリズムで "セパレータ"という概念を得ることができません。誰かが私にこれを明確にすることができますか?前もって感謝します。

  ベストアンサー

セパレータは、いくつかの接続されたコンポーネントを持つグラフを除去する頂点のサブセットです。接続されているすべてのコンポーネントが元のグラフと比較して頂点の数の半分未満を持つ場合、区切り文字はバランスされます。

By removing the balanced separator S, the grid falls apart into the connected components A and B

低いtreewidthを持つグラフには、小さなバランスのとれた区切り文字があります。より正確には、treewidth kのグラフには、最大k + 1頂点でバランスのとれた区切り文字があります。

アルゴリズムはこれを次のように利用します。

  • グラフから小さなバランス区切り文字を削除する

  • 接続されたコンポーネントの最適なソリューションを再帰的に見つける

  • セパレータを再度追加し、接続されたコンポーネントのソリューションを使用して、グラフ全体に最適なソリューションを見つけます。

上記のスキームを効率的にするには、いくつかの要件を満たす必要があります。

  • 最初のステップのセパレータは小さい(つまり、定数サイズ)

  • 2番目のステップの接続されたコンポーネントは、元のグラフ(つまり、一定の端数、例えば1/2)よりもかなり小さい頂点数です。

  • 上記のプロパティは誘導されたサブグラフに継承されます(そうでなければ効率的に再帰することはできません)

  • 接続されたコンポーネントの部分的な最適なソリューションは、グラフ全体の最適なソリューションに効率的に組み合わせることができます

これらの要件は、最後のものを除いて、低いtreewidthのグラフによって満たされます。これは最適化問題ごとに固有のものです。これは、アルゴリズムデザイナーが研究論文を書いたものです。

(頂点セパレータのウィキペディアの記事から取得した画像)

  同じタグがついた質問を見る

treedynamic-programminggraph-theorygraph-algorithm