特定のノードセットを含む最小接続サブグラフ

Question

加重されていない接続されたグラフがあります。特定のノードのセットを間違いなく含む接続されたサブグラフを見つけたいと思います。これはどのように達成できますか？

念のため、より正確な言語を使用して質問を言い換えます。 g（v、e）を、無重く、無向の接続グラフとします。 nをVのサブセットとします。G（v、e）の最小の接続されたサブグラフg（v '、e'）を見つけるための最良の方法は何ですか？

近似は問題ありません。

Answer 1

最適なソリューションを見つけるための効率的なアルゴリズムは考えられませんが、入力グラフが密度が高いと仮定すると、以下は十分に機能する可能性があります。

1. 入力グラフを変換します G(V, E) 加重グラフに G'(N, D), 、 どこ N あなたがカバーしたい頂点のサブセットであり、 D 元のグラフの対応する頂点間の距離（パス長）です。これにより、エッジに必要のないすべての頂点が「崩壊」します。

2. 最小スパニングツリーを計算します G'.

3. 次の手順で最小スパニングツリーを「拡張」します：すべてのエッジの d 最小スパニングツリーで、グラフの対応するパスを取ります G 結果セットへのパスにすべての頂点（エンドポイントを含む）を追加します V' 結果セットへのパス内のすべてのエッジ E'.

このアルゴリズムは、最適ではないソリューションを提供するために簡単に登ります。例：角に頂点、側面の中間点、三角形の中央、および側面に沿って角から角から三角形の中央まで縁がある垂直三角形。コーナーを覆うには、三角形の単一の中間点を選ぶのに十分ですが、このアルゴリズムは側面を選択するかもしれません。それにもかかわらず、グラフが密度が高い場合、それは正常に動作するはずです。

Answer 2

これはまさに有名なNPハードです シュタイナーツリー 問題。インスタンスがどのように見えるかについての詳細がなければ、適切なアルゴリズムについてアドバイスをするのは困難です。

Answer 3

最も簡単なソリューションは次のとおりです。

a）MSTに基づく： - 最初に、VのすべてのノードはV 'にあります - グラフg（v、e）の最小スパニングツリーを構築します - それをTと呼びます。
- ループ：nにないtのすべての葉Vについて、v 'からvを削除します。
-Tのすべての葉がNになるまでループを繰り返します。

b）別のソリューションは、最短のパスツリーに基づく次のものです。
- nでノードを選択し、vを呼び出し、vをツリーt = {v}のルートとします。 -NからVを削除します。

• ループ：1）Tの任意のノードから最短パスを選択し、Nの任意のノードを選択します。 v 'に追加されます。 3）PおよびNのすべてのノードは、Nから削除されます。

アルゴリズムの先頭に：既知の効率的なアルゴリズムを使用して、Gのすべての最短パスを計算します。

個人的には、私はこのアルゴリズムを私の論文の1つで使用しましたが、分散環境により適しています。 nを相互接続する必要があるノードのセットとします。グラフGの最小接続ドミネーションセットを構築したいと考えています。Nでノードを優先したいと考えています。各ノードUA一意の識別子ID（U）を提供します。 uがnにある場合、w（u）= 0とします。そうでなければw（1）。各ノードuに対してペア（w（u）、id（u））を作成します。

• 各ノードuは、マルチセットリレーノードを構築します。つまり、各2ホップ隣人がm（u）の少なくとも1つのノードの隣人であるように、1ホップneigbhorsのセットm（u）。 [最小M（U）、解決策が優れています]。

• uは、すべての隣人の中で最小のペア（w（u）、id（u））を持っている場合にのみv 'にあります。またはuはm（v）で選択されます。ここで、vは最小（w（u）、id（u））を持つuの1ホップ隣接です。

- このアルゴリズムを集中的に実行するときのトリックは、2ホップの隣人の計算に効率的であることです。 O（n^3）から得られる最善は、マトリックスの乗算によるO（n^2.37）です。

- 私は本当にこの最後の解決策の近似定量とは何かを知りたいと思います。

シュタイナーツリーのヒューリスティックのためのこの参照が好きです：シュタイナーツリーの問題、ファンフランク。リチャーズ・ダナ1955-冬のパウエル1952

Answer 4

以下を実行しようとすることができます。

1. 作成 最小限の頂点カバー 目的のノード用 N.

2. これら、おそらく接続されていないサブグラフを「大きな」ノードに崩壊させます。つまり、サブグラフごとにグラフから削除し、新しいノードに置き換えます。このノードのセットを呼び出します N'.

3. ノードの最小限の頂点カバーを実行します N'.

4. ノードを「解凍」します N'.

特定のバウンドなど内に近似を与えるかどうかはわかりません。おそらく、アルゴリズムをだまして、本当に愚かな決定を下すこともできます。