カット (グラフ理論)

グラフ理論におけるカット：最小カット、最大カット、そしてその応用

グラフ理論において、グラフを2つの部分集合に分割することをカットと呼びます。この分割において、異なる部分集合に属する頂点を結ぶ辺をカットエッジと定義します。カットのサイズは、カットエッジの総数（重み付きグラフの場合は重み合計）で表されます。フローネットワークにおいては、始点集合から終点集合への辺の重み合計で定義されます。

カットのサイズを返す関数をカット関数と言い、これは劣モジュラ関数であり、かつ正モジュラ関数であるという重要な性質を持ちます。

最小カット

最小カットとは、カットの中でサイズが最小となるカットのことです。最小カット問題は、最大フロー最小カット定理によって最大フロー問題と密接に関連付けられています。この定理は、ネットワークにおける最大流量が、始点と終点を分離するカットの最小容量に等しいことを主張しています。

最小カットを求める効率的なアルゴリズムとして、フォード・ファルカーソンアルゴリズムや永持・茨木アルゴリズムなどが知られています。無向グラフにおいて、最小カットのサイズは辺連結度とも呼ばれ、グラフの頑健性を測る指標となります。すべての最小カットはカクタスと呼ばれるグラフ構造で表現できるため、様々なアルゴリズムに応用されています。最小カット問題は線形計画問題として定式化でき、その双対問題は最大フロー問題となります。

最大カット

最大カットとは、カットの中でサイズが最大となるカットのことです。最小カット問題とは対照的に、最大カット問題はNP完全問題であり、多項式時間で解くアルゴリズムは知られていません。

最大カット問題に対する解法としては、ランダムに頂点を2つの集合に振り分ける単純なアルゴリズムや、GoemansとWilliamsonによる0.878近似アルゴリズムなどがあります。Goemans-Williamsonアルゴリズムは半正定値計画問題を解くことで近似解を求めます。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.
H. Nagamochi, and T. Ibaraki, Algorithmic Aspects of Graph Connectivity, Cambridge University Press, Cambridge, (2008)
石川, グラフカット (チュートリアル) 情報処理学会研究報告. CVIM, 2007(31), 193-204, (2007)

もう一度検索