最大カット

グラフにおいて、最大カットとは、そのサイズが少なくとも他のどのカットのサイズよりも大きいカットのことです。つまり、グラフの頂点を2つの補集合 $S$ と $T$ に分割し、 $S$ と $T$ の間の辺の数が最大になるようにすることです。このようなカットを見つけることは、最大カット問題として知られています。

この問題は、次のように簡単に説明できます。頂点集合のサブセット $S$ と補完サブセット間の辺の数が可能な限り大きくなるようなサブセット $S$ を求めます。同様に、可能な限り多くの辺を持つグラフの二部サブグラフを求めます。

この問題には、重み付き最大カットと呼ばれるより一般的なバージョンがあります。このバージョンでは、各辺に実数 (重み )が関連付けられており、目的は辺の数ではなく、 $S$ とその補辺の間の辺の合計重みを最大化することです。正と負の両方の重みを許容する重み付き最大カット問題は、すべての重みの符号を反転することで、重み付き最小カット問題に簡単に変換できます。

下限

エドワーズ^[1]^[2]は、 $n$ 頂点 $m$ 辺グラフ $G$ 上のMax-Cutの以下の2つの下限値を得た（(a)では $Gは$ 任意であるが、(b)ではGは連結である）。

(ア)

\left\lceil {\frac {m}{2}}+{\sqrt {{\frac {m}{8}}+{\frac {1}{64}}}}-{\frac {1}{8}}\right\rceil

（ロ）

{\frac {m}{2}}+{\frac {n-1}{4}}.

境界(b)は、エルデシュが予想したため、エドワーズ-エルデシュ境界^[3]と呼ばれることが多い。エドワーズは確率的手法を用いてエドワーズ-エルデシュ境界を証明した。クロウストンら^[4]は、線型代数と擬似ブール関数の解析を用いてこの境界を証明した。

Crowston らの証明により、 Edwards-Erdős 境界を、各辺に + または – が割り当てられている符号付きグラフ $G$ $= ($ $V$ $,$ $E$ $,$ $s$ $)$ 上のバランスのとれたサブグラフ問題( BSP ) ^[4]に拡張することができます。 $Vをサブセット$ $U$ と $W$ に分割する場合、辺 $xy$ がバランスしているのは、 $s$ $($ $xy$ $) = +$ かつ $x$ と $y$ が同じサブセット内にあるか、 $s$ $($ $xy$ $) = -$ かつ $x$ と $y が異なるサブセット内にある場合です。 BSP は、$ $G$ 内のバランスのとれた辺の最大数 $b$ $($ $G$ $)$ を持つ分割を見つけることを目的とします。 Edwards-Erdős は、接続されたすべての符号付きグラフ $Gに対して$ $b$ $($ $G$ $)$ の下限値を与えます。境界 (a) は、三角形のないグラフ、最大次数が与えられたグラフ、 $H$ のないグラフなどの特別なクラスのグラフに対して改善されました。たとえば、^[5]^[6]^{[7]を参照してください。}

PoljakとTurzik ^[8]はエドワーズ-エルデシュ境界を重み付きMax-Cutに拡張した。

{\frac {w(G)}{2}}+{\frac {w(T_{min})}{4}},

ここで $w (G)$ と $w (Tmin)はそれぞれ$ $G$ とその最小重み全域木 $Tmin$ の重みである。最近、GutinとYeo ^[9]は、任意の重み付きグラフに対するPoljak-Turzik境界と重み付きグラフの特別なクラスに対する境界を拡張して、重み付きMax-Cutの下限をいくつか得た $。$

計算の複雑さ

最大カットに関連する次の決定問題は、理論計算機科学において広く研究されてきました。

グラフGと整数kが与えられた場合、 G内に少なくともkの大きさのカットがあるかどうかを判断します。

この問題はNP完全であることが知られています。問題がNPであることは簡単にわかります。つまり、十分に大きなカットを提示することで、答えが「はい」であることは簡単に証明できます。問題のNP完全性は、たとえば、最大2充足可能性（最大充足可能性問題の制約）からの削減によって示されます。^[10]決定問題の重み付きバージョンは、Karpの21のNP完全問題の1つでした。^{[11] Karpは、}分割問題からの削減によってNP完全性を示しました。

上記の決定問題の標準的な最適化変種は、通常、最大カット問題または最大カットと呼ばれ、次のように定義されます。

グラフGが与えられた場合、最大カットを見つけます。

最適化バリアントは NP 困難であることが知られています。反対の問題、つまり最小カットを見つける問題は、 Ford-Fulkerson アルゴリズムによって効率的に解決できることが知られています。

アルゴリズム

多項式時間アルゴリズム

最大カット問題はNP 困難であるため、一般的なグラフにおける最大カットの多項式時間アルゴリズムは知られていません。

平面グラフ

しかし、平面グラフでは、最大カット問題は経路検査問題（グラフの各辺を少なくとも 1 回訪れる最短の巡回経路を見つける問題）の双対である。つまり、グラフGの最大カットセットに属さない辺は、 Gの双対グラフの最適検査巡回で 2 重になる辺の双対である。最適検査巡回は、平面を 2 つの部分集合、つまり曲線の巻き数が偶数である点の部分集合と巻き数が奇数である点の部分集合に分ける自己交差曲線を形成する。この 2 つの部分集合は、巡回中に双対が奇数回出現するすべての辺を含むカットを形成する。経路検査問題は多項式時間で解くことができ、この双対性により、平面グラフの最大カット問題も多項式時間で解くことができる。^[12]ただし、最大二分問題は NP 困難であることが知られている。^[13]

近似アルゴリズム

最大カット問題はAPX困難であり^[14]、つまりP = NPでない限り、最適解に任意に近い多項式時間近似スキーム（PTAS）は存在しない。したがって、既知の多項式時間近似アルゴリズムはすべて、1未満の近似比を達成する。

単純なランダム化0.5近似アルゴリズムが存在する。各頂点についてコインを投げて、それをパーティションのどの半分に割り当てるかを決定する。^[15]^{[16]予想されるように、エッジの半分はカットエッジです。このアルゴリズムは}、条件付き確率法を使用して非ランダム化できるため、単純な決定論的多項式時間 0.5 近似アルゴリズムも存在します。^[17]^[18]このようなアルゴリズムの 1 つは、指定されたグラフの頂点の任意のパーティションから開始し、一度に 1 つの頂点をパーティションの一方から他方へ繰り返し移動し、このタイプの改善がこれ以上行われなくなるまで、各ステップでソリューションを改善します。反復回数が最大であるのは、アルゴリズムが各ステップで少なくとも 1 つのエッジでカットを改善するためです。アルゴリズムが終了すると、すべての頂点に接続するエッジの少なくとも半分がカットに属します。そうでない場合、頂点を移動するとカットが改善されるからです。したがって、カットには少なくとも個のエッジが含まれます。 $G=(V,E)$ $|E|$ $|E|/2$

最もよく知られている近似比を持つMax-Cutの多項式時間近似アルゴリズムは、半正定値計画法とランダム丸め法を用いたGoemansとWilliamsonによる手法であり、近似比が $\alpha \approx 0.878,$

\alpha ={\frac {2}{\pi }}\min _{0\leq \theta \leq \pi }{\frac {\theta }{1-\cos \theta }}.

^[19]^[20]

ユニークゲーム予想が正しい場合、これは最大カットの最良の近似比です。^[21]このような証明されていない仮定がなければ、最大カット値をよりも良い近似比で近似することはNP困難であることが証明されています。^[22]^[23] ${\tfrac {16}{17}}\approx 0.941$

^[24]では、オープンソースの実装を含む、この問題に対する10のヒューリスティックの拡張分析が行われています。

パラメータ化されたアルゴリズムとカーネル化

少なくとも (パラメータ) kのサイズのカットを見つける問題が固定パラメータで扱いやすい (FPT) ことを証明するのは簡単ですが、グラフ G に少なくとも Edwards-Erdős の下限 (上記の下限を参照) プラス (パラメータ) kのサイズのカットがあるかどうかを決定する問題に対して固定パラメータで扱いやすいことを示すのははるかに困難です。Crowston ら^{[25] は、}問題が時間内に解くことができ、サイズのカーネルを許容することを証明しました。Crowston ら^{[25] は、}固定パラメータで扱いやすいという結果を Balanced Subgraph Problem (BSP、上記の下限を参照) に拡張し、カーネルサイズをに改善しました(BSP にも当てはまります)。Etscheid と Mnich ^{[26] は、} BSP の固定パラメータで扱いやすいという結果をに改善し、カーネルサイズの結果を頂点に改善しました。 $8^{k}O(n^{4})$ $O(k^{5})$ $O(k^{3})$ $8^{k}O(m)$ $O(k)$

アプリケーション

機械学習

最大カットアルゴリズムは、ノードを特徴として、エッジを距離として扱い、グラフを2つの十分に分離されたサブセットに分割します。言い換えれば、バイナリ分類を実行するために自然に適用できます。より一般的な分類アルゴリズムと比較して、特徴空間を必要とせず、要素間の距離のみを必要とします。^[27]

理論物理学

統計物理学と無秩序系において、最大カット問題はスピングラス模型のハミルトニアンを最小化することと等価であり、最も簡単に言えばイジング模型である。^[28]グラフG上のイジング模型と最近傍相互作用のみの場合、ハミルトニアンは

H[s]=-\sum _{ij\in E(G)}J_{ij}s_{i}s_{j}

ここで、グラフの各頂点iはスピン値を取ることができるスピンサイトです。スピン配置は、スピンアップとスピンダウンの2つのセットに分割されます。2つのセットを接続するエッジの集合で表します。ハミルトニアンは次のように書き直すことができます。 $s_{i}=\pm 1.$ $V(G)$ $V^{+}$ $V^{-}.$ $\delta (V^{+})$

{\begin{aligned}H[s]&=-\sum _{ij\in E(V^{+})}J_{ij}-\sum _{ij\in E(V^{-})}J_{ij}+\sum _{ij\in \delta (V^{+})}J_{ij}\\&=-\sum _{ij\in E(G)}J_{ij}+2\sum _{ij\in \delta (V^{+})}J_{ij}\\&=C+2\sum _{ij\in \delta (V^{+})}J_{ij}\end{aligned}}

このエネルギーを最小化することは、最小カット問題と同等であり、グラフの重みを最大カット問題として設定することと同等である。^[28] $w_{ij}=-J_{ij},$

回路設計

最大カット問題はVLSI設計に応用されている。^[28]

参照

最小カット
最小kカット
奇数サイクル横断、最大の二部誘導部分グラフを求めることと同等
無限グラフに関連する概念である非友好的分割

注記

^ エドワーズ（1973年）。
^ エドワーズ（1975年）。
^ ビルカ、イジク、トゥザ（1999年）。
^ ab Crowston et al. (2014).
^ アロン、クリベレヴィッチ、スダコフ（2005年）。
^ スコット（2005年）。
^ Zeng & Hou (2017).
^ ポリャク＆トゥルジク（1986年）。
^ グティン＆イエオ（2021年）。
^ ギャリー＆ジョンソン（1979年）。
^ カープ（1972年）。
^ ハドロック（1975年）。
^ ヤンセンら（2005年）。
^ Papadimitriou & Yannakakis (1991) はMaxSNPの完全性を証明しています。
^ Mitzenmacher & Upfal (2005)、セクション6.2。
^ モトワニとラガヴァン (1995)、セクション。 5.1.
^ Mitzenmacher & Upfal (2005)、セクション6.3。
^ クーラー、ラーガヴァチャリ＆ヤング (2007).
^ ガウル＆クリシュナムルティ（2007年）。
^ オーシエロら（2003）
^ Khot et al. (2007).
^ ハスタッド（2001）
^ トレヴィサンら (2000)
^ ダニング、グプタ、シルバーホルツ（2018）
^ ab クロウストン、ジョーンズ、ムニッヒ (2015).
^ Etscheid & Mnich (2018).
^ Boykov, YY; Jolly, M.-P. (2001). 「ND 画像内のオブジェクトの最適な境界と領域セグメンテーションのためのインタラクティブグラフカット」。Proceedings Eighth IEEE International Conference on Computer Vision。ICCV 2001。第 1 巻。IEEE Comput. Soc。pp. 105–112。doi :10.1109/iccv.2001.937505。ISBN 0-7695-1143-0.S2CID 2245438 。
^ abc Barahona, Francisco; Grötschel, Martin; Jünger, Michael; Reinelt, Gerhard (1988). 「統計物理学と回路レイアウト設計への組み合わせ最適化の応用」.オペレーションズ・リサーチ. 36 (3): 493–513. doi :10.1287/opre.36.3.493. ISSN 0030-364X. JSTOR 170992.

参考文献

Alon, N.; Krivelevich, M.; Sudakov, B. (2005)、「Hフリーグラフにおける最大カット」、Combin. Probab. Comput.、14 : 629–647、doi :10.1017/S0963548305007017 (2024 年 11 月 1 日非アクティブ)、S2CID 123485000{{citation}}: CS1 maint: DOI inactive as of November 2024 (link)。
Ausiello, Giorgio; Crescenzi, Pierluigi; Gambosi, Giorgio; Kann, Viggo; Marchetti-Spaccamela, Alberto; Protasi, Marco (2003)、『複雑性と近似：組み合わせ最適化問題とその近似可能性特性』、Springer。

最大カット（最適化バージョン）は、付録 B（399 ページ）の問題 ND14 です。

Bylka, S.; Idzik, A.; Tuza, I. (1999)、「最大カット: Edwards-Erd6s 不等式の改良と局所アルゴリズム類似体」、Discrete Math.、194 (1–3): 39–58、doi : 10.1016/S0012-365X(98)00115-0。
Crowston, R.; Fellows, M.; Gutin, G.; Jones, M.; Kim, EJ; Rosamond, F.; Ruzsa, IZ; Thomassé, S.; Yeo, A. (2014)、「GF(2) 上の線形方程式系の半分以上を満たす: 多変量アプローチ」、J. Comput. Syst. Sci.、80 (4): 687–696、doi : 10.1016/j.jcss.2013.10.002。
Crowston, R.; Gutin, G.; Jones, M.; Muciaccia, G. (2013)、「下限値を超えてパラメータ化された最大バランスサブグラフ問題」、Theor. Comput. Sci.、513 : 53–64、arXiv : 1212.6848、doi : 10.1016/j.tcs.2013.10.026。
Crowston, R.; Jones, M.; Mnich, M. (2015)、「Edwards–Erdős 境界を超えるパラメータ化された Max-cut」、Algorithmica、72 (3): 734–757、doi :10.1007/s00453-014-9870-z、S2CID 14973734。
Dunning, Iain; Gupta, Swati; Silberholz, John (2018)、「何が最も効果的か? Max-Cut と QUBO のヒューリスティックの体系的評価」、INFORMS Journal on Computing、30 (3): 608–624、doi :10.1287/ijoc.2017.0798、S2CID 485706。
Edwards, CS (1973)、「二部グラフのいくつかの極限特性」、Can. J. Math.、25 (3): 475–485、doi : 10.4153/CJM-1973-048-x、S2CID 121925638。
Edwards, CS (1975)、「最大二部グラフの辺の数の下限の改良」、グラフ理論の最近の進歩、pp. 167–181。
Etscheid, M.; Mnich, M. (2018)、「大規模カットを見つけるための線形カーネルと線形時間アルゴリズム」、Algorithmica、80 (9): 2574–2615、doi : 10.1007/s00453-017-0388-z、hdl : 11420/4693、S2CID 16301072。
ゲイリー、マイケル・R. ;ジョンソン、デビッド・S. (1979)、「コンピュータと扱いにくさ：NP完全性理論へのガイド」、WHフリーマン、ISBN 978-0-7167-1045-5。

最大カット（決定版）は付録A2.2の問題ND16です。

最大二部サブグラフ（決定バージョン）は、付録A1.2の問題GT25です。

Gaur, Daya Ram; Krishnamurti, Ramesh (2007)、「LP 丸めと拡張」、Gonzalez, Teofilo F. (編)、『近似アルゴリズムとメタヒューリスティックスのハンドブック』、Chapman & Hall/CRC。
Goemans, Michel X. ; Williamson, David P. (1995)、「半正定値計画法を用いた最大カットおよび充足可能性問題に対する改良近似アルゴリズム」、Journal of the ACM、42 (6): 1115–1145、doi : 10.1145/227683.227684、S2CID 15794408。
Gutin, G. ; Yeo, A. (2021)、「最大加重カットの下限値」、arXiv : 2104.05536 [math.CO]。
ハドロック、F. (1975)、「多項式時間で平面グラフの最大カットを見つける」、SIAM J. Comput.、4 (3): 221–225、doi :10.1137/0204019。
Håstad, Johan (2001)、「いくつかの最適な近似不可能性の結果」、Journal of the ACM、48 (4): 798–859、doi :10.1145/502090.502098、S2CID 5120748。
Jansen, Klaus; Karpinski, Marek ; Lingas, Andrzej; Seidel, Eike (2005)、「平面グラフと幾何グラフの MAX-BISECTION に対する多項式時間近似スキーム」、SIAM Journal on Computing、35 (1): 110–119、CiteSeerX 10.1.1.62.5082、doi :10.1137/s009753970139567x。
Karp, Richard M. (1972)、「組合せ問題における縮約可能性」、Miller, RE; Thacher, JW (編)、『コンピュータ計算の複雑性』、Plenum Press、pp. 85–103。
Khot, Subhash ; Kindler, Guy; Mossel, Elchanan; O'Donnell, Ryan (2007)、「MAX-CUT およびその他の 2 変数 CSP の最適な近似不可能性の結果?」、SIAM Journal on Computing、37 (1): 319–357、doi :10.1137/S0097539705447372、S2CID 2090495。
Khuller, Samir; Raghavachari, Balaji; Young, Neal E. (2007)、「Greedy methods」、Gonzalez, Teofilo F. (ed.)、近似アルゴリズムとメタヒューリスティックスのハンドブック、Chapman & Hall/CRC。
ミッツェンマッハー、マイケル、アップファル、エリ（2005）、確率とコンピューティング：ランダム化アルゴリズムと確率分析、ケンブリッジ。
モトワニ, ラジーブ; Raghavan、Prabhakar (1995)、ランダム化アルゴリズム、ケンブリッジ。
Newman、Alantha (2008)、「Max Cut」、Kao、Ming-Yang (編)、Encyclopedia of Algorithms、Springer、pp. 489–492、doi :10.1007/978-0-387-30162-4_219、ISBN 978-0-387-30770-1。
Papadimitriou, Christos H. ; Yannakakis, Mihalis (1991)、「最適化、近似、および複雑性クラス」、Journal of Computer and System Sciences、43 (3): 425–440、doi : 10.1016/0022-0000(91)90023-X。
Poljak, S.; Turzik, Z. (1986)、「保証された最悪のケース境界を持つ特定のサブグラフ最適化問題に対する多項式時間ヒューリスティック」、Discrete Math.、58 (1): 99–104、doi : 10.1016/0012-365X(86)90192-5。
スコット、A. (2005)、「賢明な分割と関連する問題」、組合せ論の調査、ロンドン数学会講義ノートシリーズ、327：95–117。
トレヴィサン、ルカ、ソルキン、グレゴリー、スーダン、マドゥ、ウィリアムソン、デイビッド (2000)、「ガジェット、近似、線形計画法」、第 37 回 IEEE コンピュータサイエンスの基礎に関するシンポジウムの議事録: 617–626。
Zeng, Q.; Hou, J. (2017)、「 Hフリーグラフの二部サブグラフ」、 Bull. Aust. Math. Soc.、30 (3): 1–13、doi :10.1017/S0004972716001295。

外部リンク

Pierluigi Crescenzi、Viggo Kann、Magnús Halldórsson、Marek Karpinski、Gerhard Woeginger (2000)、「Minimum Cut」、「NP 最適化問題の概要」。
Andrea Casini、Nicola Rebagliati (2012)、「Max Cut を解決するための Python ライブラリ」

[1] エドワーズ（1973年）。

[2] エドワーズ（1975年）。

[3] ビルカ、イジク、トゥザ（1999年）。

[Crowston_2014-4] Crowston et al. (2014).

[5] アロン、クリベレヴィッチ、スダコフ（2005年）。

[6] スコット（2005年）。

[7] Zeng & Hou (2017).

[8] ポリャク＆トゥルジク（1986年）。

[9] グティン＆イエオ（2021年）。

[10] ギャリー＆ジョンソン（1979年）。

[11] カープ（1972年）。

[12] ハドロック（1975年）。

[13] ヤンセンら（2005年）。

[14] Papadimitriou & Yannakakis (1991) はMaxSNPの完全性を証明しています。

[15] Mitzenmacher & Upfal (2005)、セクション6.2。

[16] モトワニとラガヴァン (1995)、セクション。 5.1.

[17] Mitzenmacher & Upfal (2005)、セクション6.3。

[18] クーラー、ラーガヴァチャリ＆ヤング (2007).

[19] ガウル＆クリシュナムルティ（2007年）。

[20] オーシエロら（2003）

[21] Khot et al. (2007).

[22] ハスタッド（2001）

[23] トレヴィサンら (2000)

[24] ダニング、グプタ、シルバーホルツ（2018）

[Crowston_2015-25] クロウストン、ジョーンズ、ムニッヒ (2015).

[26] Etscheid & Mnich (2018).

[27] Boykov, YY; Jolly, M.-P. (2001). 「ND 画像内のオブジェクトの最適な境界と領域セグメンテーションのためのインタラクティブグラフカット」。Proceedings Eighth IEEE International Conference on Computer Vision。ICCV 2001。第 1 巻。IEEE Comput. Soc。pp. 105–112。doi :10.1109/iccv.2001.937505。ISBN 0-7695-1143-0.S2CID 2245438 。

[:0-28] Barahona, Francisco; Grötschel, Martin; Jünger, Michael; Reinelt, Gerhard (1988). 「統計物理学と回路レイアウト設計への組み合わせ最適化の応用」.オペレーションズ・リサーチ. 36 (3): 493–513. doi :10.1287/opre.36.3.493. ISSN 0030-364X. JSTOR 170992.