algorithm - 多項式時間で二分割を見つける

Question

入力(n、頂点の数)のサイズで多項式時間で2分割を見つけるにはどうすればよいですか? 出来ますか？頂点の数は同じままである必要があり、削除するエッジはできるだけ少なくすることができます。多項式時間は、O(n)、O(n^2)、または単に O(n) を意味しますか?

ノードを 2 つの異なるセットに配置する BFS を実行したはずですが、複雑さは O(V+E) であり、これは私が望んでいるものではありません。

助言がありますか？ありがとうございました。

Answer 1

通常、最適解はNP 困難ですが、多くの多項式ヒューリスティックが存在します。単純なアルゴリズムについては、Kernighan-Linを参照してください。

宿題ではなく現実の問題を解決しようとしている場合は、既存のパーティショナーを検索する方がよい場合があります。特に METIS ファミリでは、多くのライブラリが利用可能です。