graph - 如何选择包含任意 k 个节点的图的最小子图

Question

我正在尝试解决以下问题。它就像 k-minimum-spanning-tree 和 steiner tree 问题，但它是有图的。

• 我们有一个非负无向加权图 G = (V, E)。
• 对于每对顶点 v1 和 v2 都存在一条边 e12。换句话说，每个顶点都连接到所有其他顶点。
• 我们将创建包含 k 个顶点的顶点 U 的子集。
• 我们的目标是选择 U 中的 n 个顶点，使 U 中每个顶点到其他所有顶点的边之和最小。换句话说，我们要选择 U 中的顶点，使 U 中的节点向外的所有边的总和最小。
• 1 < n < 顶点数

我是否正确认为 k-MST 或 Steiner 树近似解都不起作用？如果是这样，这个问题叫什么？解决方案是什么？我可以使用启发式或近似法来解决这个问题，不需要正式证明。

Answer 1

我不知道是否有更快的算法，但最简单的算法(如果我的解释正确的话)是:

• 构建一个数组/映射，其中保存从 vi 到任何其他顶点的每条边的权重总和。如果您考虑图形的矩阵表示，其中每一行/列都是一个顶点，每个单元格都是边上的权重。该数组将是每一行的总和。
• 生成所有k大小的顶点子集，保留总和最小的那个。

如果有 n 个顶点，这是探索 n!/(k! (n-k)!) 这样的组合。