複数のルート頂点を持つグラフの最小スパニングツリー

Question

これらのルート頂点のすべての間のルート頂点のセットを与えられた有向グラフで最小スパニングツリー（最適分岐）を計算するアルゴリズムがあるかどうかを知りたいと思います。グラフ内の1つのルート頂点と他のすべての頂点だけではありません。ルート頂点[1,4,6]及び次画像上のようなグラフGのセットが与えられると

：

... algorighmは緑サブようなものを返すべき同じ絵の上に - グラフ。

アルゴリズムに提供されているすべてのルート頂点を接続するMSTを取得したいと思います。私は-だろうアルゴリズムの結果は、すべてのルートの頂点といくつかの他の頂点G.

から

ノート含まグラフGのサブグラフであることを考える傾向がある：

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

Answer 1

最小スパニングツリーは、すべての頂点にまたがるものとします。私はあなたが実際にはSteiner Tree問題を扱っているかもしれないと思う、それらのサブセットを接続する必要があるだけだと思う​​。残念なことに、無向エッジの伝統的なシュタイナーツリーの問題はすでにNP完備であるため、あなたの前には厳しい道があります。