algorithm - 在图中找到一个切点，将图分成大约等于两个子图

Question

有没有一种实用的算法（不是NP-hard）可以将一个图切割成两个大致相等的子图（例如，一个子图有40％-50％的顶点），同时证明切割是最小的给定两个子图的顶点数大致相等的情况下可能的切割？

Answer 1

这并不是最稀疏的切割；它是平衡切工，也是 NP 硬切，如Dasgupta、Papadimitriou 和 Vazirani 的第 8 章所述。最稀疏切割问题的规范版本不允许指定分区大小。

关于图划分问题有两种研究方向：具有最坏情况近似保证的算法，其中 Arora–Rao–Vazirani 是您感兴趣的主要结果，以及没有最坏情况保证的算法，通过其实际性能进行评估（我没有经验的随机示例：METIS）。尽管我不是很了解，但我倾向于引导你走向后一种工作；先验地，O(√log n) bicriteria 近似并不是一个非常有用的保证，并且可能首先需要一些非平凡的算法工程来让 ARV 在规模上很好地工作。