是否有一种实用的算法(不是 NP-hard)可以将一个图分成两个大约相等的子图(例如,一个子图有 40%-50% 的顶点),在同时,证明在两个子图的顶点数近似相等的情况下,割是最小可能割?
最佳答案
这并不是最稀疏的切割;它是平衡切割,也是 NP-hard,如 Chapter 8 of Dasgupta, Papadimitriou, and Vazirani 中所述.最稀疏切割问题的规范版本不允许指定分区大小。
关于图划分问题的研究有两个流派:具有最坏情况近似保证的算法,其中 Arora–Rao–Vazirani 是您感兴趣的主要结果,以及没有最坏情况保证的算法,由他们的实际表现(我没有经验的随机示例:METIS)。尽管我不是很了解,但我倾向于引导您进行后一种工作;先验的,O(√log n) 双准则近似并不是一个非常有用的保证,并且可能有一些非平凡的算法工程可以让 ARV 首先在规模上良好运行。
关于algorithm - 在图中找到一个切割,将图划分为大约相等的两个子图,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/16581699/