指定された頂点数での最小カットのための効率的なアルゴリズム

Question

頂点のあるグラフを考えてみましょう $V$ そしてエッジ $E$. 。最小カット問題の標準バージョンでは、次のパーティションを見つけます。 $V$ (空ではない) サブセットに $C$ とその補足 $\bar{C}$ 間に入るエッジの数を最小限に抑えるため $C$ そして $\bar{C}$. 。この問題に対しては、多項式時間で解決するアルゴリズムが知られています。私の質問は、次の制約を追加で指定した場合はどうなるかということです。 $ | c | = n $ いくつかのための $n < |V|$?つまり、次のセットを見つけたいのです。 $n$ 残りの頂点に接続する最小数のエッジを持つ頂点。この場合にも効率的なアルゴリズムはあるのでしょうか?私は、この問題が多項式時間で形式的に解決できるかどうか (おそらくそうであると推測します) という問題と、実際にはどのようなアルゴリズムが最適であるかという両方に興味があります。

Answer 1

のために $n= \frac {|V|} 2$, 、それは最小二分法と呼ばれ、NP 困難です。が存在します $O(\log^{3/2} n)$-近似値: 「最小二等分値の多対数近似」.

興味がある場合は、より一般的な問題は同じサイズの複数のコンポーネントに分割することであり、これはバランス グラフ パーティショニングと呼ばれます。3 つ以上の部分については、P=NP でない限り、有限近似は存在しません。 「バランスの取れたグラフ分割」 (Andreev、Rakke), 答えが 0 かどうかを効率的に確認することができないためです。

部品のバランスが必ずしも正確に揃っていない場合 (多少の不均衡は許容されます)、 $O(\log n)$-近似アルゴリズムが存在します: 「ツリーとアプリケーションのバランスの取れたパーティション」.

---

いくつかのアルゴリズム (こちらも確認してください) https://en.wikipedia.org/wiki/Graph_partition および次の論文の「参考文献」セクション):

• さまざまな種類のローカル検索:まずいくつかの分割から始めて、パーツ間の頂点を交換してカットを最小限に抑えます。例えば。各頂点の「ゲイン」を計算し（別のパーツに移動すると改善されます）、最大ゲインで頂点を交換します。この利点は、他のアルゴリズムの後に適用できることです。

• スペクトル分割 (例: スペクトルグラフ理論とグラフ分割):ラプラシアン行列の 2 番目の固有ベクトルを使用して分割を近似します (例:最小のものを動かすことで $|V|/2$ 最初の部分への座標）。驚くほどうまく機能します。ただし、不均衡な二等分が必要な場合に適用できるかどうかはわかりません（例: $1:2$ の代わりに $1:1$).

• 線形埋め込み: 「線形埋め込みによる分散バランス パーティショニング」. 。すべての頂点ペアの合計を最小限に抑えながら、頂点を 1 次元配列に埋め込みます。それらの間の距離にエッジの重みを掛けたものです。次に、この配列を必要なサイズの連続したチャンクに分割するだけです。私の経験ではそれほどうまくいきませんでした。

• (広告) 私たちの論文: 「多次元バランスグラフ分割」 Projected Gradient Descend" (投影勾配降下法), ここで、勾配降下法を使用して最小二等分を見つけました。各頂点に対して、頂点が最初の部分に属する確率を大まかに表す変数を導入し、カットを最小限に抑えると二次関数の制約付き最適化になります。実際には、細かく調整されたローカル検索よりもパフォーマンスが少し劣りますが、複数のバランス制約がある場合には非常にうまく機能します。

スペクトル法を除けば、それらはすべて、グラフを任意の比率で分割するために簡単に適用できます。

標準ソルバーもあります。 カヒップ, メティス. 。私の経験では、KaHIP はかなり良かったです。ただし、任意のサイズの部分への分割をサポートしているかどうかはわかりません。