查找將圖劃分爲近似等於兩個子圖的切圖

Question

是否存在可將圖形切割成兩個的實用算法（不是NP-hard）大約等分子圖（例如，一個子圖具有40％-50％的頂點），同時，在兩個子圖具有大致相等的頂點數的情況下，證明切割是最小可能切割？

Answer 1

這不完全是最稀疏的;它是平衡切，也是NP-hard，如Chapter 8 of Dasgupta, Papadimitriou, and Vazirani中所述。最稀疏的切割問題的規範版本不允許指定分區大小。

對圖分區問題有兩個研究流：最壞情況逼近保證的算法，其中Arora-Rao-Vazirani是您感興趣的主要結果，以及沒有最壞情況保證的算法由他們的實際表現（隨機的例子，我沒有經驗：METIS）。儘管我對此不太瞭解，但我仍傾向於引導你走向後一線工作;先驗O（√logn）雙標準近似並不是一個非常有用的保證，並且可能會有一些非平凡的算法工程設計來首先使ARV在規模上良好地工作。