algorithm - 具有多个根顶点的图中的最小生成树

Question

我想知道是否有一种算法可以计算有向图中的最小生成树（最佳分支），给定所有这些根顶点之间的一组根顶点，但不仅仅是一个根顶点和图中的所有其他顶点.

给定一组根顶点 [1,4,6] 和一个图 G，如下图所示：

...算法应该在同一张图片上返回类似绿色子图的东西。

我想得到这样一个 MST，它连接提供给算法的所有根顶点。我倾向于认为可能算法的结果是图 G 的子图，其中包含 G 的所有根顶点和一些其他顶点。

笔记：

1. 我知道有向图没有 MST，但有Chu-Liu/Edmonds 算法。
2. 我猜这种算法的结果（如果实际上可能的话）将返回一个最佳分支，其中包括图的一些顶点以及所有根顶点。

Answer 1

最小生成树应该跨越所有顶点。我认为您实际上可能正在处理斯坦纳树问题，因为您只需要连接它们的一个子集。不幸的是，具有无向边的传统施泰纳树问题已经是 NP 完备的，因此您的路还很艰难。