在图中找到彼此之间最大传播/距离的 N 个节点

Question

给定一个包含 N 个节点（数千个）的图，我需要找到 K 个节点，以便使 K 的每对 (K1,K2) 之间的平均路径长度最大化。所以基本上，我想让它们尽可能远离彼此。

我将为此使用哪种算法/如何编程而不必尝试 K 的几个单一组合？

也作为扩展：如果我现在有 N 个节点，并且我需要在图中放置 2 组节点 K 和 L，以使每对 (L,K) 之间的平均路径长度最大化，我该怎么做？

我目前的尝试是只做几个随机放置，然后计算 K 和 L 对之间的平均路径长度，但这个计算开始需要很多时间，所以我不想花那么多时间只是评估随机选择的组合。我宁愿花时间获得真正最广泛的组合。

有没有什么算法可以解决这个问题？

Answer 1

坏消息是这个问题是 NP-hard 问题，是从独立集减少的。（假设单位权重。添加一个连接到所有其他顶点的新顶点；然后我们正在寻找平均距离为 2 的 K 的集合。）

如果你决定得到一个精确的解决方案（我不确定你不应该这样做），那么我会尝试分支定界，使用节点是/不是 K 之一作为分支决策和粗边界（给定 K 的一个子集，找到使它们之间的距离和到子集的距离的适当组合最大化的两个节点，然后将边界设置为包含已知节点间距离的适当加权平均值）。

如果上面的确切算法像 Evgeny 担心的那样在千节点图上阻塞，那么使用最远点聚类（链接转到 Facility Location 上的 Wikipedia 页面，其中描述了 FPC）将图切割到可管理的大小，从而导致希望小的近似误差。