最大カット問題

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

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

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

下界エドワードは個の頂点および個の辺を有するグラフにおいて最大カットに関する以下の下界を示した.: 任意のグラフの場合: 連結グラフの場合: 連結グラフで与えられた下界はそれ以前にエルデシュにより予想されていたため、エドワード・エルデシュ下界（Edwards–Erdős bound）と呼ばれている。エドワードはエドワード・エルデシュ下界をによって示し、またクロウストンらは線形代数および疑似ブール関数の解析によりこの下界を示している。

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

また、重み付き最大カットに対する下界はおよびツルジークによりエドワード・エルデシュ下界の拡張によって与えられた:

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

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

グラフおよび整数値が与えられたとき、以上ののカットが存在するか

この問題はNP完全である。この問題がNPであることは、十分に大きなカットを提示し、それが最大カットであるかを判定することで示すことができる。例として、最大カット問題はに還元することで示すことができる。重み付き最大カット問題に関してはカープは最大カット問題をに還元することでNP完全であることを示した（を参照）。

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

グラフが与えられたときに、最大カットを求める

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

アルゴリズム多項式時間

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

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

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

最大カット問題は次の単純な乱択アルゴリズムによる0.5-近似アルゴリズムが知られている: 各頂点ごとにコインを投げて、どちらか一方の分割に割り当てる; .。このとき、各辺がカットに含まれるかは辺のそれぞれの頂点がそれぞれ異なる分割に含まれるかによって決定されるため、このときカットの期待値は辺の半数となる。この乱択アルゴリズムはによって脱乱択となる。このことから、この単純なアルゴリズムは0.5-近似多項式時間アルゴリズムとなる; .。このようなアルゴリズムの一つの例としてはある与えられたグラフにおいて任意の分割から始め、各反復において一つの頂点をもう片方の分割に割り当てることを行う。これをカットの値が改善されなくなるまで、繰り返す。この方法の反復回数は各反復においてそれ以前のカットより一つの辺がカットとして選ばれるため、高々回行えばよい。反復を終えた時点ではすべての頂点に対して接続している辺の少なくとも半分がカットに含まれている。もしそうでなければ、その頂点を他の分割へ割り当てることで現在のカットを改善できるためである。このことから、カットには少なくとも本の辺が含まれている。

最大カット問題の多項式近似アルゴリズムとして最も近似度の高いものはゴーマン・ウィリアムソンによる半正定値計画問題およびによる -近似アルゴリズムである。ただし、は:

が真であると仮定すれば、この方法が最良の近似アルゴリズムとなることが知られている。この予想が成り立たないとする場合でも、近似比となる最大カットを求めることはNP困難であることが知られている; .。

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

パラメータ化・カーネル化アルゴリズム

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

理論物理学

統計力学・において最大カット問題はスピングラス模型あるいはより単純化したイジング模型におけるハミルトニアンの最小化に等しい。グラフ G でのイジング模型および最隣接相互作用に対してハミルトニアンはと表される。

ここでグラフの各頂点 i にはスピン値をもつスピンサイトとする。スピン配置はに対してスピンが上向きのものを、下向きのものをの二負の部分集合に分割する。ここで二つの集合を結ぶ辺集合をとすると、ハミルトニアンは以下のように表される:

上記のエネルギー最小化問題は最小カット問題と同等であり、とすることで最大カット問題に帰着することができる。

回路設計最大カット問題はの設計において応用されている。

脚注

参考文献 . .（最適化問題としての）最大カット問題は付録B（399ページ）の問題14に記載。 . . . . . . . . . . . （決定問題としての）最大カット問題は付録A2.2の問題ND16に記載され、（決定問題としての）最大二部グラフ問題は付録A1.2の問題GT25に記載されている。 . . . . . . . . . . . . . . . . . . . .

最大カット問題

Źródło i licencja