最大カット問題

【さいだいかっともんだい (maximum cut problem)】

無向グラフ$(V,E)\,$において, 各枝$e_{ij}\in E\ (i,j\in V,\ i\neq j)\,$に非負整数$w_{ij}\,$が重みとして付与されている. このとき

$\sum _{i\in X,\,\,j\in V-X}\ w_{ij}$

を最大にする$X\subset V\,$を求める問題. つまり, $V\,$を2つの部分集合に分割する組合せ(カット)のうち, それらの部分集合間の枝に付与された重みの総和が最大となる分割を求める.