最大カット問題 📖 Wikipedia

最大カット問題（さいだいカットもんだい、英: maximum cut problem）とは、グラフ理論における問題の一種である。あるグラフにおけるカットの中で最大のものを求める問題である。すなわち、グラフの頂点を二つの補集合 S、T に分割（英語版）するとき、S、T を結ぶ辺の数が最大となるような分割を求める問題である。

また、最大カット問題は次のように述べることができる。今、頂点集合の部分集合 S を求めるとする。このとき、S とその補集合の間にある辺の本数ができるだけ多くなることを考える。あるいは、元のグラフからできるだけ多くの辺を含む二部グラフを得る問題である。

この問題には重み付き最大カット問題（weighted max-cut）と呼ばれる最大カット問題をより一般化した問題が存在している。この場合、各辺に実数の重みが割り当てられており、目的としては部分集合 S とその補集合の間の辺の数ではなく、それらの辺の重みの総和を最大化する分割を求めることとなる。辺の重みについて負の場合も許容される場合は重み付き最大カット問題はすべての重みの符号を反転することにより、自明に重み付き最小カット問題へと変換することができる。

エドワードは n 個の頂点および m 個の辺を有するグラフ G において最大カットに関する以下の下界を示した^[1]:

• 任意のグラフの場合: ${\displaystyle \displaystyle \left\lceil {\frac {m}{2}}+{\sqrt {{\frac {m}{8}}+{\frac {1}{64}}}}-{\frac {1}{8}}\right\rceil .}$
• 連結グラフの場合: ${\displaystyle \displaystyle {\frac {m}{2}}+{\frac {n-1}{4}}.}$

連結グラフで与えられた下界はそれ以前にエルデシュにより予想されていたため、エドワード・エルデシュ下界（Edwards–Erdős bound）と呼ばれている^[2]。エドワードはエドワード・エルデシュ下界を確率的手法（英語版）によって示し、またクロウストンらは線形代数および疑似ブール関数の解析によりこの下界を示している^[3]。

エドワード・エルデシュ下界はグラフの各辺に "+"、あるいは "-" の符号が付された符号付きグラフ（英語版） G = (V, E, s) に対する平衡部分問題（Balanced Subgraph Problem; BSP）に拡張することができる。ここで平衡（Balanced）とは、頂点 V を部分集合 U、W に分割するとき、辺 xy が s(xy) = + かつ頂点 x、y が同じ部分集合に含まれる、あるいは s(xy) = – かつ頂点 x、y がそれぞれ異なる部分集合に含まれる状態を指す。グラフ G に対する平衡部分問題は平衡を満たす辺の数 b(G) を最大にするような分割を求める問題である。エドワード・エルデシュ下界は任意の連結符号付グラフ G に対する b(G) の下界を与える。またエドワードによって一般のグラフに対する下界については大きさ三のクリークを持たないグラフ、最大次数が所与のグラフ、H-フリーグラフなど、特別のグラフに対して改良されてきた^[4]。

また、重み付き最大カットに対する下界はポリャク（英語版）およびツルジークによりエドワード・エルデシュ下界の拡張によって与えられた^[5]:

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

ただし、w(G) はグラフ G の重み和であり、w(T_min) は G の最小全域木 T_min の重み和を表す。グーティンおよびイョオにより一般の重み付きグラフあるいは特殊なクラスにおける重み付きグラフに対して重み付き最大カットのポリャク・ツルジーク下界を上回る下界を示している^[6]。

理論計算機科学において以下の決定問題としての最大カットは広く研究されてきた:

この問題はNP完全である。この問題がNPであることは、十分に大きなカットを提示し、それが最大カットであるかを判定することで示すことができる。例として、最大カット問題はMAX2-SAT（英語版）に還元することで示すことができる^[7]。重み付き最大カット問題に関してはカープは最大カット問題を集合分割問題（英語版）に還元することでNP完全であることを示した（カープによる21のNP完全問題（英語版）を参照）^[8]。

上記の問題の標準的な最適化問題は最大カット問題として知られ、以下のように定義される:

最適化問題としての最大カット問題はNP困難である。一方、グラフの最小カットを求める問題はフォード・ファルカーソン法を用いることで効率よく解くことができる。

最大カット問題はNP困難であるため、現時点では最大カット問題を多項式時間で解くアルゴリズムは発見されていない。

しかしながら、平面グラフに対する最大カット問題は平面グラフ G の最大カットに含まれない辺が、G の双対グラフにおいて最適な閉路の中で重複して通過される辺の双対辺に対応するため、中国人郵便配達問題（グラフの辺を少なくとも一回ずつ辿る最短の閉路を求める問題）と双対の関係にある。

最大カット問題はAPX困難（英語版）であることが知られているため^[9]、P=NP でない限り最適解に十分に近しい解を求めるような多項式時間近似スキーム（PTAS）が存在しないとされている。このことから、現在知られているすべての多項式時間アルゴリズムについて1より小さな近似比しか示さない。

最大カット問題は次の単純な乱択アルゴリズムによる0.5-近似アルゴリズムが知られている: 各頂点ごとにコインを投げて、どちらか一方の分割に割り当てる^[10]。このとき、各辺がカットに含まれるかは辺のそれぞれの頂点がそれぞれ異なる分割に含まれるかによって決定されるため、このときカットの期待値は辺の半数となる。この乱択アルゴリズムは条件付確率的手法（英語版）によって脱乱択となる。このことから、この単純なアルゴリズムは0.5-近似多項式時間アルゴリズムとなる^[11]。このようなアルゴリズムの一つの例としてはある与えられたグラフ ${\displaystyle G=(V,E)}$ において任意の分割から始め、各反復において一つの頂点をもう片方の分割に割り当てることを行う。これをカットの値が改善されなくなるまで、繰り返す。この方法の反復回数は各反復においてそれ以前のカットより一つの辺がカットとして選ばれるため、高々 ${\displaystyle |E|}$ 回行えばよい。反復を終えた時点ではすべての頂点に対して接続している辺の少なくとも半分がカットに含まれている。もしそうでなければ、その頂点を他の分割へ割り当てることで現在のカットを改善できるためである。このことから、カットには少なくとも ${\displaystyle |E|/2}$ 本の辺が含まれている。

最大カット問題の多項式近似アルゴリズムとして最も近似度の高いものはゴーマン・ウィリアムソンによる半正定値計画問題および乱択丸め法（英語版）による ${\displaystyle \alpha \approx 0.878}$-近似アルゴリズムである。ただし、αは:

${\displaystyle \displaystyle \alpha ={\frac {2}{\pi }}\min _{0\leq \theta \leq \pi }{\frac {\theta }{1-\cos \theta }}.}$^[12]

ユニークゲーム予想（英語版）が真であると仮定すれば、この方法が最良の近似アルゴリズムとなることが知られている^[13]。この予想が成り立たないとする場合でも、近似比 ${\displaystyle {\tfrac {16}{17}}\approx 0.941}$ となる最大カットを求めることはNP困難であることが知られている^[14]。

ダニングらは最大カット問題に対する十種類のアルゴリズムに関する比較を行っている^[15]。

頂点を特徴量、辺を特徴量間の距離とみなすことで、最大カット問題に対するアルゴリズムはそれらの特徴量を二つのクラスに分類することができる。言い換えれば、自然に二値分類される。最大カットアルゴリズムは他のアルゴリズムと比較すると、特徴量空間を定義する必要がなく、特徴量間の距離のみを与えることでアルゴリズムにより分割を実行することができる^[16]。

統計力学・無秩序系（英語版）において最大カット問題はスピングラス模型あるいはより単純化したイジング模型におけるハミルトニアンの最小化に等しい^[17]。グラフ G でのイジング模型および最隣接相互作用に対してハミルトニアンは ${\displaystyle H[s]=-\sum _{ij\in E(G)}J_{ij}s_{i}s_{j}}$ と表される。

ここでグラフの各頂点 i にはスピン値 ${\displaystyle s_{i}=\pm 1}$ をもつスピンサイトとする。スピン配置は ${\displaystyle V(G)}$ に対してスピンが上向きのものを ${\displaystyle V^{+}}$、下向きのものを ${\displaystyle V^{-}}$ の二負の部分集合に分割する。ここで二つの集合を結ぶ辺集合を ${\displaystyle \delta (V^{+})}$ とすると、ハミルトニアンは以下のように表される:

${\displaystyle {\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}}}$

上記のエネルギー最小化問題は最小カット問題と同等であり、${\displaystyle w_{ij}=-J_{ij},}$ とすることで最大カット問題に帰着することができる^[17]。

最大カット問題は超大規模集積回路（英語版）の設計において応用されている^[17]。

• Alon, N.; Krivelevich, M.; Sudakov, B. (2005). “Maxcut in H-free graphs”. Combinatorics, Probability and Computing 14: 629–647. doi:10.1017/S0963548305007017. .
• Ausiello, Giorgio; Crescenzi, Pierluigi; Gambosi, Giorgio; Kann, Viggo; Marchetti-Spaccamela, Alberto; Protasi, Marco (2003). Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties. Springer .（最適化問題としての）最大カット問題は付録B（399ページ）の問題14に記載。
• Barahona, Francisco; Grötschel, Martin; Jünger, Michael; Reinelt, Gerhard (1988). “An application of combinatorial optimization to statistical physics and circuit layout design”. Operations Research 36 (3): 493–513. doi:10.1287/opre.36.3.493. ISSN 0030-364X. JSTOR 170992. .
• Boykov, Y.Y.; Jolly, M.-P. (2001). “Interactive graph cuts for optimal boundary & region segmentation of objects in N-D images”. 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. http://dx.doi.org/10.1109/iccv.2001.937505 .
• Bylka, S.; Idzik, A.; Tuza, I. (1999). “Maximum cuts: Improvements and local algorithmic analogues of the Edwards-Erd6s inequality”. Discrete Mathematics 194 (1–3): 39–58. doi:10.1016/S0012-365X(98)00115-0. .
• Crowston, R.; Fellows, M.; Gutin, G.; Jones, M.; Kim, E. J.; Rosamond, F.; Ruzsa, I. Z.; Thomassé, S. et al. (2014). “Satisfying more than half of a system of linear equations over GF(2): A multivariate approach”. Journal of Computer and System Sciences 80 (4): 687–696. doi:10.1016/j.jcss.2013.10.002. .
• Crowston, R.; Gutin, G.; Jones, M.; Muciaccia, G. (2013). “Maximum balanced subgraph problem parameterized above lower bound”. Theoretical Computer Science 513: 53–64. arXiv:1212.6848. doi:10.1016/j.tcs.2013.10.026. .
• Crowston, R.; Jones, M.; Mnich, M. (2015). “Max-cut parameterized above the Edwards–Erdős bound”. Algorithmica 72 (3): 734–757. doi:10.1007/s00453-014-9870-z. .
• Dunning, Iain; Gupta, Swati; Silberholz, John (2018). “What works best when? A systematic evaluation of heuristics for Max-Cut and QUBO”. INFORMS Journal on Computing 30 (3): 608–624. doi:10.1287/ijoc.2017.0798. .
• Edwards, C. S. (1973). “Some extremal properties of bipartite subgraphs”. Canadian Journal of Mathematics 25 (3): 475–485. doi:10.4153/CJM-1973-048-x. .
• Edwards, C. S. (1975). “An improved lower bound for the number of edges in a largest bipartite subgraph”. Recent Advances in Graph Theory. pp. 167–181 .
• Etscheid, M.; Mnich, M. (2018). “Linear Kernels and Linear-Time Algorithms for Finding Large Cuts”. Algorithmica 80 (9): 2574–2615. doi:10.1007/s00453-017-0388-z. hdl:11420/4693. .
• Garey, Michael R.; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 978-0-7167-1045-5 . （決定問題としての）最大カット問題は付録A2.2の問題ND16に記載され、（決定問題としての）最大二部グラフ問題は付録A1.2の問題GT25に記載されている。
• Gaur, Daya Ram; Krishnamurti, Ramesh (2007). “LP rounding and extensions”. In Gonzalez, Teofilo F.. Handbook of Approximation Algorithms and Metaheuristics. Chapman & Hall/CRC .
• Goemans, Michel X.; Williamson, David P. (1995). “Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming”. Journal of the ACM 42 (6): 1115–1145. doi:10.1145/227683.227684. .
• Grötschel, M.; Jünger, M.; Reinelt, G. (1987). “Calculating exact ground states of spin glasses: a polyhedral approach”. Heidelberg colloquium on glassy dynamics (Heidelberg, 1986). Lecture Notes in Phys.. 275. Springer, Berlin. pp. 325–353. doi:10.1007/BFb0057526. ISBN 3-540-17777-9. MR 0916885 .
• Gutin, G.; Yeo, A. (2021), “Lower Bounds for Maximum Weighted Cut”, arXiv:2104.05536 [math.CO].
• Hadlock, F. (1975). “Finding a Maximum Cut of a Planar Graph in Polynomial Time”. SIAM Journal on Computing 4 (3): 221–225. doi:10.1137/0204019. .
• Håstad, Johan (2001). “Some optimal inapproximability results”. Journal of the ACM 48 (4): 798–859. doi:10.1145/502090.502098. .
• Jansen, Klaus; Karpinski, Marek; Lingas, Andrzej; Seidel, Eike (2005). “Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs”. SIAM Journal on Computing 35 (1): 110–119. doi:10.1137/s009753970139567x. .
• Karp, Richard M. (1972). “Reducibility among combinatorial problems”. In Miller, R. E.; Thacher, J. W.. Complexity of Computer Computation. Plenum Press. pp. 85–103 .
• Khot, Subhash; Kindler, Guy; Mossel, Elchanan; O'Donnell, Ryan (2007). “Optimal inapproximability results for MAX-CUT and other 2-variable CSPs?”. SIAM Journal on Computing 37 (1): 319–357. doi:10.1137/S0097539705447372. https://repository.upenn.edu/statistics_papers/395. .
• Khuller, Samir; Raghavachari, Balaji; Young, Neal E. (2007). “Greedy methods”. In Gonzalez, Teofilo F.. Handbook of Approximation Algorithms and Metaheuristics. Chapman & Hall/CRC .
• Mitzenmacher, Michael; Upfal, Eli (2005). Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge .
• Motwani, Rajeev; Raghavan, Prabhakar (1995). Randomized Algorithms. Cambridge .
• Newman, Alantha (2008). “Max cut”. In 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). “Optimization, approximation, and complexity classes”. Journal of Computer and System Sciences 43 (3): 425–440. doi:10.1016/0022-0000(91)90023-X. .
• Poljak, S.; Turzik, Z. (1986). “A polynomial time heuristic for certain subgraph optimization problems with guaranteed worst case bound”. Discrete Math. 58 (1): 99–104. doi:10.1016/0012-365X(86)90192-5. .
• Robertson, Neil; Seymour, Paul (1993). “Excluding a graph with one crossing”. In Robertson, Neil; Seymour, Paul. Graph Structure Theory: Proc. AMS–IMS–SIAM Joint Summer Research Conference on Graph Minors. Contemporary Mathematics. 147. American Mathematical Society. pp. 669–675 .
• Sæther, Sigve Hortemo; Telle, Jan Arne (2016). “Between treewidth and clique-width”. Algorithmica 75 (1): 218–253. arXiv:1404.7758. doi:10.1007/s00453-015-0033-7. MR 3492064. .
• Scott, A. (2005). “Judicious partitions and related problems”. Surveys in Combinatorics, London Mathematical Society Lecture Note Series 327: 95–117. .
• Trevisan, Luca; Sorkin, Gregory; Sudan, Madhu; Williamson, David (2000). “Gadgets, Approximation, and Linear Programming”. Proceedings of the 37th IEEE Symposium on Foundations of Computer Science: 617–626. .
• Zeng, Q.; Hou, J. (2017). “Bipartite Subgraphs of H-free Graphs”. Bull. Aust. Math. Soc. 30 (3): 1–13. doi:10.1017/S0004972716001295. .

• 最小カット
• 最小kカット（英語版）
• 奇サイクル横断（英語版） - 最大の誘導二部グラフを求める問題と同等である。
• 無愛想分割（英語版） - 無限グラフに関連する

• Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski, Gerhard Woeginger (2000), "最大カット", in "NP最適化問題集".
• Andrea Casini, Nicola Rebagliati (2012), "最大カットを解くPythonライブラリ"