algorithm - 在图中找到一个切割，将图划分为大约相等的两个子图

Question

是否有一种实用的算法(不是 NP-hard)可以将一个图分成两个大约相等的子图(例如，一个子图有 40%-50% 的顶点)，在同时，证明在两个子图的顶点数近似相等的情况下，割是最小可能割？

Answer 1

这并不是最稀疏的切割；它是平衡切割，也是 NP-hard，如 Chapter 8 of Dasgupta, Papadimitriou, and Vazirani 中所述.最稀疏切割问题的规范版本不允许指定分区大小。

关于图划分问题的研究有两个流派:具有最坏情况近似保证的算法，其中 Arora–Rao–Vazirani 是您感兴趣的主要结果，以及没有最坏情况保证的算法，由他们的实际表现(我没有经验的随机示例:METIS)。尽管我不是很了解，但我倾向于引导您进行后一种工作；先验的，O(√log n) 双准则近似并不是一个非常有用的保证，并且可能有一些非平凡的算法工程可以让 ARV 首先在规模上良好运行。