在图中找到一条切割线，将图分成大致相等的两个子图

Question

在图中找到一条切割线，将图分成大致相等的两个子图

algorithmgraphgraph-theorygraph-algorithm

3

是否有一种实用算法（不是NP-hard问题）可以将图形分成两个大致相等的子图（例如，一个子图具有40％-50％的顶点），同时证明该切割是最小可能的切割，假设两个子图具有大致相等的顶点数？

- eddyxu

2

密切相关的问题是Sparsest cut。它是NP难问题。 - Evgeny Kluev

如果你想要一个近似的解决方案，贪婪算法和/或爬山算法可能是最简单的选择。 - Bernhard Barker

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- David Eisenstat · Accepted Answer

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

图分割问题有两个研究方向：具有最坏情况近似保证的算法，其中Arora-Rao-Vazirani是您感兴趣的主要结果，以及没有最坏情况保证的算法，其通过实际性能进行评估（我没有经验的随机示例：METIS）。尽管我不太了解它，但我倾向于引导您走向后者的方向；从先验上讲，O(√log n)双标准近似并不是非常有用的保证，并且在首次扩展ARV的过程中，可能需要一些非平凡的算法工程来使其良好运行。