カット (グラフ理論)

グラフ理論におけるカット（英: Cut）は、グラフの頂点を2つの部分集合に分割することである。G(V, E) がグラフを表すとする。カットとは、頂点の集合 V を2つの集合 S と T に分割することを指す。任意のエッジ (u,v) $\in$ E について u $\in$ S でかつ v $\in$ T（有向グラフの場合 u $\in$ T でかつ v $\in$ S の場合もある）のとき、このエッジを「カットをまたいでいる」あるいは「カットエッジ」と呼ぶ。

「カットの大きさ」は、カットをまたいでいるエッジの総数で表される。重み付けされたグラフでは、カットの大きさはカットをまたいでいるエッジの重み付けの総和で定義される。フローネットワークでは、カットの大きさは始点側から終点側へ向かうエッジの重み付けの総和で定義される（逆方向のエッジは加算されない）。

最小カットと最大カット

最小カット

最大カット

カットが最小であるとは、カットの大きさが他のいかなるカットよりも大きくないことを指す。最大フロー最小カット定理は、最大フロー（流量）が始点と終点を別々の部分集合とするカットのうちで最小なものの大きさ（カットエッジの重み付けの総和）と等しいことを意味する。最小カットを求める問題には多項式時間のアルゴリズムが存在し、フォード・ファルカーソンのアルゴリズムが有名である。

カットが最大であるとは、カットの大きさが他のいかなるカットよりも小さくないことを指す。最大カットを求める問題は、NP完全問題である。つまり、多項式時間で最大カットを求めるアルゴリズムは存在しないが、効率的に近似解を求めるメタヒューリスティックな探索手法は存在する。最大カット問題がNP完全であることの証明は、最大充足可能性問題からの変換で得られる。

平面グラフでの最大カットを求める多項式時間アルゴリズムは存在する。純粋な乱択アルゴリズムである 0.5近似アルゴリズムが存在する。最もよく知られている最大カットアルゴリズムは、Goemans と Williamson が半正定値計画とランダム化丸め算法を使って考案した 0.878近似アルゴリズムである。unique games conjecture が真である限りにおいて、このアルゴリズムは最適な近似アルゴリズムと言える。

線形計画的意味では、（たとえ、目的関数の最大と最小を入れ替えて解が得られたとしても）最小カット問題と最大カット問題は双対問題ではない。最小カット問題と双対をなすのは最大フロー問題である。

関連項目

• プリムのアルゴリズム
• エドモンズ-カープアルゴリズム

参考文献

• R. M. Karp, Reducibility among combinatorial problems, in R. E. Miller and J. W. Thacher (eds.), Complexity of Computer Computation, Plenum Press, New York, 85-103 (1972)
• M. X. Goemans, and D. P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, Journal of the ACM, 42, 6 (Nov. 1995), 1115-1145
• S. Khot, G. Kindler, E. Mossel, and R. O’Donnell, Optimal inapproximability results for MAX-CUT and other two-variable CSPs?, In Proceedings of the 45th IEEE Symposium on Foundations of Computer Science, pp. 146–154, 2004.
• Michael R. Garey and David S. Johnson (1979年). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 0-7167-1045-5.  A2.2: ND16, pg.210.