用指定数量的顶点进行最小切割的高效算法

Question

考虑带有顶点的图 $ v $ 和边缘 $ e $ 。最小剪切问题的标准版本是找到 $ v $ 的分区（非空）子集 $ C $ 及其补码 $ \ bar {c} $ 以最小化之间的边缘数量$ c $ 和 $ \ bar {c} $ 。在该问题中已知算法在多项式时间中解决了该问题。我的问题是，如果另外指定 $ | c |的约束= n $ 对于某些 $ n <| v | $ ？也就是说，我们希望找到一组 $ n $ 顶点，其中有最小的边缘连接到顶点的其余部分。在这种情况下还有高效的算法吗？我对这个问题是否在多项式时间（我猜测它是）中是正式解释的问题，也有兴趣在实践中最好的算法。

Answer 1

对于 $ n=frac {| v |} 2 $ ，它被称为最小的小分割，它是NP-HARD。存在 $ o（\ log ^ {3/2} n）$ - aggrymation：“最小平等的电动显式近似”

如果您有兴趣，越一般的问题是拆分为相同大小的多个组件，并且它被称为平衡图分区。对于超过2个部分，除非p= np：，因为您无法有效地检查答案是否为0。

如果部件不一定完全平衡（允许小的不平衡），则存在 $ o（\ log n）$ - aggryatimation算法存在：“树木和应用程序的平衡隔板”

---

一些算法（也检查 https://en.wikipedia.org/wiki/graph_partigation和以下论文的“参考文献”部分）：

• 本地搜索各种口味：我们从一些分区开始，然后尝试在部件之间交换顶点以最小化切割。例如。我们计算每个顶点的“增益”（如果我们将其移动到另一个部分），并交换具有最大增益的顶点。它的优点是您可以在任何其他算法之后应用它。

频谱分区（参见光谱图理论和图形分区）：使用拉普拉斯矩阵的第二个特征向量来近似分区（例如，通过移动最小的 $ | v | / 2 $ 坐标到第一个部分）。令人惊讶的是。但是，当您想要不平衡的分配时，我不确定它可以适应这种情况（例如 $ 1：2 $ 而不是 $ 1：1 $ ）。

• 线性嵌入：“通过线性嵌入”“分布式平衡分区。我们将顶点嵌入一维阵列，同时最小化所有顶点的总和：它们之间的距离乘以其边缘的重量。然后我们刚将此数组拆分到连续大小的连续块中。在我的经验中没有那么好。

• （广告）我们的论文：“多维平衡图通过 预定的渐变渐变“，我们使用梯度下降来查找最小分块：对于每个顶点，我们引入一个变量，该变量大致表示顶点所属的概率，并最大限度地减少切割减少到受约束的优化二次函数。通过微调的本地搜索，它在实践中有点优先表现，但是当您有多个余额约束时，它会很好地工作。

除了光谱法之外，所有这些都可以术语调整以在任意比例中对图进行分区。

还有标准求解器： kahep ， metis 。在我的经历中，Kahip非常好。我不确定他们支持拆分成任意尺寸的部分。