algorithm - 複数のルート頂点を持つグラフの最小全域木

Question

これらすべてのルート頂点間のルート頂点のセットが与えられた有向グラフで最小スパニング ツリー (最適分岐) を計算するアルゴリズムがあるかどうかを知りたいのですが、グラフ内の 1 つのルート頂点と他のすべての頂点だけではありません。 .

ルート頂点のセット [1,4,6] と、次の図のようなグラフ G があるとします。

...アルゴリズムは、同じ画像の緑色のサブグラフのようなものを返す必要があります。

アルゴリズムに提供されたすべてのルート頂点を接続するような MST を取得したいと思います。私は、自称アルゴリズムの結果は、すべてのルート頂点と G の他のいくつかの頂点を含むグラフ G のサブグラフであると考える傾向があります。

ノート：

1. 有向グラフの MST がないことは知っていますが、Chu–Liu/Edmonds アルゴリズムはあります。
2. このようなアルゴリズムの結果 (実際に可能であれば) は、グラフのいくつかの頂点とすべてのルート頂点を含む最適な分岐を返すと思います。

Answer 1

最小スパニング ツリーは、すべての頂点にまたがることになっています。それらのサブセットのみを接続する必要があることを考えると、実際にシュタイナー木の問題を扱っている可能性があると思います。残念ながら、無向辺を使用する従来のシュタイナー木問題はすでに NP 完全であるため、困難な道のりが待っています。