algorithm - グラフをほぼ 2 つのサブグラフに分割するグラフのカットを見つける

Question

グラフを2つのほぼ等しいサブグラフにカットできる実用的なアルゴリズム（NPハードではない）はありますか（たとえば、1つのサブグラフには40％から50％の頂点があります）、その間、カットが最小であることを証明します2 つのサブグラフの頂点数がほぼ等しいという条件で、可能なカットは?

Answer 1

これは正確に最もまばらなカットではありません。Dasgupta、Papadimitriou、および Vazirani の第 8 章で説明されているように、これはバランスの取れたカットであり、NP 困難でもあります。最も疎なカット問題の標準バージョンでは、パーティション サイズを指定できません。

グラフ分割問題に関する研究には 2 つの流れがあります。Arora–Rao–Vazirani が主な関心のある結果である、最悪の場合の近似を保証するアルゴリズムと、実際のパフォーマンスによって評価される最悪の場合の保証のないアルゴリズムです。 (経験のないランダムな例: METIS )。私はそれについてよく知りませんが、後者の仕事にあなたを導く傾向があります。アプリオリに、O(√log n) 二基準近似は非常に有用な保証ではありません。また、ARV を大規模にうまく機能させるには、自明ではないアルゴリズム エンジニアリングが必要になる可能性があります。