algorithm - 将图划分为连接的子图，这些子图的顶点集必须位于同一子图中

Question

我有一个连通的无向图 G = (V, E)，一个集合 S = {S_1, S_2,..., S_n} 其中每个 S_i 都是 V 的一个子集，并且 k > 1。我怎样才能将 V 分成 k 个子集，这样可以保证:

1. 对于每个i，S_i中的每个节点都在同一个子集中
2. 每个子集代表 G 的一个连通子图？

Answer 1

Steiner 森林问题是，给定一个加权图 G = (V, E) 和顶点对 (s₁, t₁), …, (s _m, t_m), 找到 G 的最轻边子图 H，使得对于所有 i，顶点 s_i 和 t_i属于H的同连通分量。

问题的决策版本本质上是具有单位权重的 Steiner 森林的决策版本。不幸的是，这种特殊情况仍然是 NP-hard。

从 Steiner 森林的特殊情况到您的问题的简化是，给定一个未加权的 Steiner 森林实例和确定是否存在成本最多为 c 的解决方案的说明，使用相同的图创建您的问题的实例， k = |V| - c，并且对于所有 i，令 S_i = {s_i, t_i}。如果存在成本至多为 c 的 Steiner 森林，那么森林的连通分量就是您的子集，其数量至少为 |V| - c = k。相反，如果你的问题的实例有一个解决方案，那么我们可以在你的每个子集中找到一个生成树，并且总成本最多为 |V| - k = c。

已知的最佳近似比率是 2，如果 k 很小，这对您没有多大帮助。您可能必须使用分支定界法。