将一个图分割成连接子图，其中一些顶点集必须在同一个子图中。

Question

我有一个连通的无向图 G = (V, E)，一个集合 S = {S_1, S_2,..., S_n}，其中每个 S_i 是 V 的子集，以及一个 k > 1。如何将 V 划分为 k 个子集，以确保：

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

- zoo

---

属于math.stackexchange.com。 - spraff

这个数字 k 是预先固定的还是取决于解决方案？ - Grigor Gevorgyan

我假设S_i是不相交的？而且我猜测n>k？ - Nicolas78

还有哪些顶点不属于任何S？（如果没有，你的生活就变得更容易了;) - Nicolas78

Answer 1

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

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

从Steiner forest问题的特殊情况到你的问题的约简是，给定Steiner forest问题的非加权实例和确定是否存在成本不超过c的解决方案的指令，创建与相同图形的你的问题的实例，k = | V | - c，并且对于所有i，让S_i = {s_i，t_i}。如果存在成本不超过c的Steiner forest，则该森林的连通分量是你的子集，其数量至少为| V |-c = k。反之，如果你的问题的实例有解，则我们可以在每个你的子集中找到一棵生成树，总成本不超过| V |-k = c。

已知的最佳近似比是2，如果k很小，这并没有帮助你。你可能需要使用分支定界算法。

- cutting plane

---

检查每个S_i是否为连通子图（否则问题将无解）。这不是正确的：考虑实例V = {1，2，3，4，5}和E = {{1, 2}，{2, 3}，{3, 4}，{4, 5}}以及S1 = {1，3}，S2 = {2，4}和S3 = {5}和k = 2。 S1和S2都不能形成一个连通子图，但解{{1，2，3，4}，{5}}是有效的。 - cutting plane

你的回答看起来像是在那些时刻正在寻找的理论推导类型。问题只是我不懂它。成本从哪里开始发挥作用？ - Nicolas78

@Nicolas78 这里的“cost”是指森林中边的数量。我可能应该说“总权重”，以免混淆概念 - 计算机科学在这方面很糟糕。对于森林而言，关键方程式是 #components + #edges = #vertices。Steiner森林解决方案的效率是以边数为度量单位，而此问题的解决方案的效率是以组件（=连接子集）为度量单位。 - cutting plane

Answer 2

一些随机的观察。您可能无法连接两个S_i，S_j，因为它们不形成一个连通子图。由于图是连通的，如果您只添加足够多的其他S_k，就可以始终将它们连接起来 - 最终您将得到完全由定义连接的完整图。因此，连通性要求驱使您合并。然而，k个子集的要求则驱使您保持分离状态。基本上，您有一个n^k搜索空间，如果您跟踪这些条件，可以彻底削减它。当然，如果您在没有S的自由节点中，那么游戏就会完全改变。

嗯，不是真正的答案，而是一个开始。无论如何都会发布 ;)

- Nicolas78