最大カット問題

同義語:最大カットmaximum cut problemmax-cut problemMAX CUT

概要

最大カット問題(maximum cut problem)とは、辺に非負の重みのついたグラフの頂点を 2 つに分け、2 つの側にまたがる辺の重みの和を最大にする問題で、重みが 1 なら辺の最も多い二部部分グラフを探すことと同じである。$\pm1$ の変数の 2 次形式の最小化とも言い換えられ、反強磁性 Ising モデルの基底状態にあたる。重みつきの判定問題は部分和問題からの帰着で NP 完全であり、無作為なカットは最適値の半分、Goemans–Williamson の半正定値緩和は $0.878$ 倍を保証する。$16/17$ を超える比は $\mathrm{P}=\mathrm{NP}$ でない限り達成できず、Unique Games 予想のもとでは $0.878$ が最良である。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 二部グラフ, NP完全, 期待値の線形性

最大カット問題(maximum cut problem、MAX CUT)は、辺に非負の重みのついたグラフの頂点を 2 つに分け、2 つの側にまたがる辺の重みの和を最大にする問題である(WS11 §5.1、p. 107)。重みがすべて $1$ なら、辺の本数が最大の 二部グラフ である部分グラフを探すことと同じである。
同じ「カット」でも、2 点 $s,t$ を分けるカットの重みを 最小 にする問題は 最大流最小カット定理 により多項式時間で解ける。これに対して最大カット問題は NP 困難であり、最適解の代わりに最適値の何割を保証できるかが問題になる。どのグラフでも辺の半分はまたがせられる(離散数学 の定理「辺の半分以上を横切る分割」)。半正定値計画 を使う Goemans–Williamson の方法は $0.878$ 倍を保証し、この比は Unique Games予想 のもとで改良できない。
この記事では、問題の定式化と言い換え(prop-mc-quadratic)、最大値の基本的な性質と例(prop-mc-basic、ex-mc-petersen)、マッチングを使う下界(thm-mc-matching)を述べ、重みつきの問題が NP 困難であることを部分和問題からの帰着で証明する(thm-mc-np-hard)。近似の上限と下限は表にまとめる。

定義

この記事のグラフは有限の単純グラフ $G=(V,E)$ とし、$n=\lvert V\rvert$、$m=\lvert E\rvert$ とする。辺 $\{i,j\}$ を $ij$ と書く。

カットと最大カット問題

$U\subset V$ に対し、一方の端点が $U$、他方の端点が $V\setminus U$ にある辺の集合を $\delta(U)$ と書き、$U$ の定める カット という。$U$ と $V\setminus U$ は同じカットを定める。辺の重み $w\colon E\to\mathbb{R}_{\ge0}$ が与えられたとき、$w(\delta(U))=\sum_{ij\in\delta(U)}w_{ij}$ をカットの 重み といい、
$$ \mathrm{mc}(G,w)=\max_{U\subset V}w(\delta(U)) $$
を求める問題を 最大カット問題 という。重みがすべて $1$ のときの値を $\mathrm{mc}(G)=\max_U\lvert\delta(U)\rvert$ と書く。判定問題としては、$G$、整数の重み $w$、整数 $k$ を受け取り、$w(\delta(U))\ge k$ となる $U$ があるかを問う。

$U$ は $2^n$ 個しかないので最大値はいつも存在する。判定問題は NP に属する:$U$ を証拠として与えれば、$w(\delta(U))\ge k$ は辺を 1 本ずつ見て確かめられる。
$\delta(U)$ の辺だけを残した部分グラフは、$U$ と $V\setminus U$ を 2 つの側とする二部グラフである。逆に、$G$ の部分グラフ $H=(V,F)$ が二部グラフで $V=U\sqcup(V\setminus U)$ と二部分割されるなら $F\subset\delta(U)$ である。したがって $\mathrm{mc}(G)$ は、二部グラフである $G$ の部分グラフの辺の本数の最大値に等しい。

言い換え:±1 の 2 次形式

2 次形式による表示

$V=\{1,\dots,n\}$ とし、$U\subset V$ に $y_i=1$($i\in U$)、$y_i=-1$($i\notin U$)で $y\in\{-1,1\}^n$ を対応させる。$W=\sum_{ij\in E}w_{ij}$、重みつきの Laplace行列 を $L_w$ とすると
$$ w(\delta(U))=\frac14\sum_{ij\in E}w_{ij}(y_i-y_j)^2=\frac14\,y^{\mathsf T}L_wy=\frac12\Bigl(W-\sum_{ij\in E}w_{ij}y_iy_j\Bigr) $$
である。したがって最大カット問題は、$\sum_{ij\in E}w_{ij}y_iy_j$ を $y\in\{-1,1\}^n$ の上で最小にする問題と同じである。

辺ごとに値を比べる

辺 $ij$ について、$ij\in\delta(U)$ なら $y_i=-y_j$ なので $(y_i-y_j)^2=4$、$y_iy_j=-1$ であり、そうでなければ $(y_i-y_j)^2=0$、$y_iy_j=1$ である。よって $\frac14(y_i-y_j)^2$ と $\frac12(1-y_iy_j)$ はどちらも辺 $ij$ がカットに入るかの指示関数であり、$w_{ij}$ を掛けて足せば 1 つ目と 3 つ目の等号を得る。2 つ目の等号は $L_w$ の定義 $y^{\mathsf T}L_wy=\sum_{ij\in E}w_{ij}(y_i-y_j)^2$ による。$\square$

$y_i$ をスピン、$-w_{ij}$ を相互作用と読むと、$\sum w_{ij}y_iy_j$ は反強磁性の Isingモデル のエネルギーで、最大カットはその基底状態にあたる。この表示の $y_iy_j$ を単位ベクトルの内積に緩めたものが、半正定値計画 の記事の「最大カット問題の緩和」である。

基本的な性質と例

$G$ の 奇閉路 とは、長さが奇数の閉路をいう。

最大値の基本的な性質
  1. $\mathrm{mc}(G)=m$ であるのは、$G$ が二部グラフのとき、かつそのときに限る。
  2. どのカット $\delta(U)$ も、$G$ の各奇閉路の辺を少なくとも 1 本含まない。したがって、辺を共有しない奇閉路が $r$ 本あれば $\mathrm{mc}(G)\le m-r$ である。
  3. 頂点が $n$ 個の 完全グラフ $K_n$ では $\mathrm{mc}(K_n)=\lfloor n^2/4\rfloor$ である。長さ $n$ の閉路 $C_n$ では、$n$ が偶数なら $\mathrm{mc}(C_n)=n$、奇数なら $n-1$ である。
閉路の上で側が入れ替わる回数を数える

1:$\mathrm{mc}(G)=m$ なら、$U$ と $V\setminus U$ が全部の辺をまたがせる二部分割である。逆も二部分割をそのまま $U$ にとればよい。
2:奇閉路 $v_0v_1\cdots v_{\ell-1}v_0$($\ell$ は奇数)をたどると、カットの辺を通るたびに $U$ の内外が入れ替わり、一周して $v_0$ に戻るので、入れ替わりの回数は偶数である。$\ell$ は奇数なので、閉路の辺のうちカットに入らないものが少なくとも 1 本ある。辺を共有しない $r$ 本の奇閉路では、カットに入らない辺が少なくとも $r$ 本ある。
3:$K_n$ では、$\lvert U\rvert=a$ のカットの辺はちょうど $a(n-a)$ 本で、その最大は $a=\lfloor n/2\rfloor$ のときの $\lfloor n/2\rfloor\lceil n/2\rceil=\lfloor n^2/4\rfloor$ である。$C_n$ は $n$ が偶数なら二部グラフなので 1 による。$n$ が奇数なら 2 で $\mathrm{mc}\le n-1$ であり、頂点を順に交互に $U$ と $V\setminus U$ に入れると、最後の辺 $v_{n-1}v_0$ 以外はまたがるので $n-1$ が達成される。$\square$

$K_{2k}$ では $\mathrm{mc}=k^2$、$m=k(2k-1)$ なので、またがせられる辺の割合は $k/(2k-1)\to\frac12$ である。「どのグラフでも辺の半分以上」という下界の定数 $\frac12$ が改良できないことは、離散数学 の例「定数 1/2 は改良できない」で示されている。

Petersen グラフの最大カット

Petersenグラフ $P$(頂点 10、辺 15)では $\mathrm{mc}(P)=12$ である。
上界:$\mathrm{mc}(P)\ge13$ とすると、カットに入らない辺が 2 本以下で、その 2 本を除いた部分グラフは二部グラフになるから、$P$ のすべての奇閉路がその 2 本のどちらかを通る。$P$ には長さ 5 の閉路がちょうど 12 本あり、どの辺もちょうど 4 本の 5 閉路に含まれる(有限の数え上げで確かめられる。$12\times5=15\times4$ と合う)。2 本の辺が通る 5 閉路は高々 $8$ 本で、$12$ 本に足りないので矛盾する。
下界:外側の 5 閉路を $a_0\cdots a_4$、内側の星形を $b_0b_2b_4b_1b_3$、スポークを $a_ib_i$ とする。$U=\{a_0,a_2,b_3,b_4\}$ とすると、カットに入らない辺は $a_3a_4$、$b_0b_2$、$a_1b_1$(スポーク)の 3 本で、カットの辺は $12$ 本である。
$P$ の奇閉路は長さ 5 以上なので、辺を共有しない奇閉路を 3 本とると 15 本の辺がすべて使われ、各頂点の次数 3 が閉路ごとの次数 2 の和(偶数)になって矛盾する。外側と内側の 5 閉路の 2 本はとれるので、prop-mc-basic の 2 の上界は $13$ にとどまる。この例は、辺を共有しない奇閉路の数による上界が等号にならないことを示している。

下界:マッチングを使う

辺の半分という下界は、各頂点を独立に確率 $\frac12$ で $U$ に入れたときの期待値から出る(近似アルゴリズム の命題「無作為なカット」)。頂点の入れ方に少しだけ相関をつけると、下界を上げられる。辺を共有しない辺の集合を マッチング という(マッチング(グラフ理論))。

マッチングによる下界

$w\ge0$ を辺の重み、$W=\sum_{ij\in E}w_{ij}$ とし、$M\subset E$ をマッチングとする。すると
$$ \mathrm{mc}(G,w)\ \ge\ \frac{W+w(M)}2 $$
である。とくに重みがすべて $1$ で、$G$ に $\mu$ 本の辺からなるマッチングがあれば $\mathrm{mc}(G)\ge(m+\mu)/2$ である。

マッチングの辺の両端を必ず分ける

頂点を 組 に分ける。$M$ の辺 $ij$ ごとに $\{i,j\}$ を 1 つの組とし、$M$ のどの辺の端点でもない頂点はそれぞれ 1 点だけの組とする。組ごとに独立に、次のように $U$ を選ぶ:2 点の組 $\{i,j\}$ では確率 $\frac12$ ずつで「$i\in U$、$j\notin U$」か「$j\in U$、$i\notin U$」のどちらかにし、1 点の組 $\{v\}$ では確率 $\frac12$ ずつで $v\in U$ か $v\notin U$ にする。どの頂点も確率 $\frac12$ で $U$ に入る。
$M$ の辺 $ij$ は必ずカットに入る。$M$ に属さない辺 $uv$ について、$u$ と $v$ は異なる組にある。同じ組の 2 点を結ぶ $G$ の辺は $M$ の辺だけだからである。組の選び方は独立なので、$u\in U$ と $v\in U$ は独立な事象で、それぞれ確率 $\frac12$ をもつ。よって $uv$ がカットに入る確率は $\frac12\cdot\frac12+\frac12\cdot\frac12=\frac12$ である。期待値の線形性により、カットの重みの期待値は
$$ w(M)+\frac{W-w(M)}2=\frac{W+w(M)}2 $$
であり、確率変数はいつも期待値より小さいことはないので、この値以上の重みのカットがある。$\square$

この下界と証明は、近似アルゴリズム の「無作為なカット」の議論を組に分けて行ったもので、この記事で書き下ろした。$K_{2k}$ は $k$ 本の辺からなるマッチングをもつので、下界は $(k(2k-1)+k)/2=k^2=\mathrm{mc}(K_{2k})$ となり、等号が成り立つ(prop-mc-basic の 3)。一方 $C_{2k+1}$ では、$\mu=k$ から下界は $(3k+1)/2$ で、最大値 $2k$ より小さい($k\ge2$)。

主定理:重みつきの問題は NP 困難

部分和問題 とは、正の整数 $a_1,\dots,a_n$ と整数 $T$ を受け取り、$\sum_{i\in I}a_i=T$ となる $I\subset\{1,\dots,n\}$ があるかを問う判定問題である。部分和問題は NP 困難である(Eri19 §12.12、pp. 402–404。頂点被覆問題からの帰着による。この記事では証明しない)。

重みつき最大カット問題の NP 完全性

最大カット問題の判定問題(def-mc-cut、重みは非負の整数)は NP 完全である。重みを正の整数に限り、グラフを完全グラフに限っても NP 困難である。

部分和問題を完全グラフのカットに埋め込む

NP に属することは def-mc-cut の後で見た。部分和問題の入力 $a_1,\dots,a_n,T$ から、多項式時間で最大カット問題の入力を作り、答えが一致するようにする。$A=\sum_ia_i$ とおく。$T<0$ または $T>A$ なら答えは「いいえ」なので、答えが「いいえ」の固定した入力(たとえば頂点 2 個、辺の重み $1$、$k=2$)を出力する。以下 $0\le T\le A$ とする。
数を 2 つ足す。 $b_i=a_i$($1\le i\le n$)、$b_{n+1}=A+T$、$b_{n+2}=2A-T$ とおく。どれも正の整数で、$\sum_{i=1}^{n+2}b_i=4A$ である。頂点 $1,\dots,n+2$ の完全グラフに重み $w_{ij}=b_ib_j$ をつけ、$k=4A^2$ とする。各数の 2 進表示の長さは入力の長さの定数倍以下なので、この入力は多項式時間で作れる。
カットの重みは積になる。 $U\subset\{1,\dots,n+2\}$ について $s=\sum_{i\in U}b_i$ とおくと、
$$ w(\delta(U))=\sum_{i\in U}\sum_{j\notin U}b_ib_j=s(4A-s)=4A^2-(s-2A)^2 $$
である。したがって $w(\delta(U))\ge k$ となる $U$ があるのは、$\sum_{i\in U}b_i=2A$ となる $U$ があるときに限る。
和が $2A$ の部分集合と部分和問題の解は対応する。 $\sum_{i\in I}a_i=T$ なら、$U=I\cup\{n+2\}$ について $\sum_{i\in U}b_i=T+2A-T=2A$ である。逆に $\sum_{i\in U}b_i=2A$ とする。$b_{n+1}+b_{n+2}=3A>2A$ なので、$n+1$ と $n+2$ がともに $U$ に入ることはない。補集合の和も $4A-2A=2A$ なので、ともに $U$ の外にあることもない。必要なら $U$ を補集合に取り替えて $n+2\in U$、$n+1\notin U$ としてよい。すると $I=U\setminus\{n+2\}\subset\{1,\dots,n\}$ について $\sum_{i\in I}a_i=2A-(2A-T)=T$ である。
以上で、部分和問題の答えと作った入力の答えが一致する。重みは正の整数で、グラフは完全グラフである。$\square$

この証明は、部分和問題を「和を半分ずつに分ける問題」に直し、それを積の重みのカットに写すもので、この記事で書き下ろした。帰着で作る重みは入力の数の積なので大きく、この証明は重みが大きい場合の難しさを示すにとどまる。重みがすべて $1$ の最大カット問題も NP 困難である(Eri19 §12.13、p. 406 は MAX 2SAT からの帰着で示せると述べる。この記事では証明しない)。

近似の保証と限界

最大カット問題の $\alpha$-近似 とは、どの入力に対しても重みが $\alpha\cdot\mathrm{mc}(G,w)$ 以上のカットを多項式時間で出す手順をいう(乱択の手順では期待値で測る。近似アルゴリズム の定義に従う)。重みは非負とする。$\alpha_{\mathrm{GW}}=\min_{0<\theta\le\pi}\frac2\pi\frac{\theta}{1-\cos\theta}=0.878\ldots$ とおく。

比 $\alpha$主張所在
$\frac12$無作為なカット、またはその脱乱択化で達成できる近似アルゴリズム(WS11 Theorem 5.3、p. 107)
$\alpha_{\mathrm{GW}}$半正定値緩和と無作為な超平面で達成できる(Goemans–Williamson)半正定値計画(WS11 Theorem 6.9、p. 145)
$\alpha>\frac{16}{17}\approx0.941$達成できれば P $=$ NP(Håstad)WS11 Theorem 6.10、p. 147
$\alpha>\alpha_{\mathrm{GW}}$Unique Games 予想のもとで、達成できれば P $=$ NP(Khot–Kindler–Mossel–O'Donnell)Unique Games予想(WS11 Theorem 6.11、p. 147)

$\frac{16}{17}$ と $\alpha_{\mathrm{GW}}$ の間で、多項式時間で達成できる比の上限がどこにあるかは、Unique Games 予想が未解決なので決まっていない。Theorem 6.10 は Håstad(2001)、Theorem 6.11 は Khot–Kindler–Mossel–O'Donnell(2007)と Mossel–O'Donnell–Oleszkiewicz の結果による(WS11 p. 159 の章末の注)。
半正定値緩和の値 $Z$ は $\mathrm{mc}(G,w)\le Z$ を満たす上界で、Goemans–Williamson の議論から $\mathrm{mc}(G,w)\ge\alpha_{\mathrm{GW}}Z$ も出る(WS11 pp. 145–147)。上界の側では、prop-mc-quadratic と Rayleigh 商から $\mathrm{mc}(G,w)\le\frac n4\lambda_{\max}(L_w)$ も得られる(半正定値計画 の命題「緩和の上下の評価」)。

反例:条件を外すと成り立たないこと

外す条件・主張反例成り立たなくなること
重みが非負辺 1 本の道で重み $-1$$\mathrm{mc}=0$ だが無作為なカットの期待値は $-\frac12$。比による保証が意味を失う
最大ではなく局所最適$C_4$(頂点 $1,2,3,4$)で $U=\{1,2\}$どの 1 頂点を動かしてもカットは増えないが、カットは $2$ で最大値 $4$ の半分
二部グラフ奇閉路 $C_{2k+1}$$\mathrm{mc}=m$ が成り立たない($\mathrm{mc}=m-1$)
奇閉路による上界の等号Petersen グラフ上界 $13$ に対し $\mathrm{mc}=12$(ex-mc-petersen)
表の確かめを開く

1 行目:カットは $U=\emptyset$ で重み $0$、2 頂点を分けると $-1$ なので最大値は $0$。各頂点を確率 $\frac12$ で入れると辺がまたがる確率は $\frac12$ で、期待値は $-\frac12$ である。2 行目:$C_4$ の辺は $12,23,34,41$。$U=\{1,2\}$ ではカットの辺は $23,41$ の 2 本である。$1$ を外に出すと $\{12,23\}$、$2$ を外に出すと $\{12,41\}$、$3$ を入れると $\{34,41\}$、$4$ を入れると $\{23,34\}$ で、どれも 2 本である。一方 $U=\{1,3\}$ では 4 本すべてがまたがる。局所最適の解が最大値の半分以上であることは 離散数学 の定理「辺の半分以上を横切る分割」の 1 つ目の証明による。3・4 行目は prop-mc-basic と ex-mc-petersen による。

歴史と出典

辺を確率 $\frac12$ ずつで分けると期待値が辺の重みの総和の半分になることは、Erdős の 1967 年の論文(二部部分グラフについて)にある(WS11 p. 139 の章末の注)。半正定値計画による $0.878$-近似は Goemans と Williamson が与え、半正定値計画を近似アルゴリズムに使った最初の例である(WS11 p. 159)。prop-mc-quadratic・prop-mc-basic・thm-mc-matching・thm-mc-np-hard の証明と、ex-mc-petersen はこの記事で書き下ろした。Petersen グラフの 5 閉路の数え上げは有限の計算である。

関連項目

参考文献

[1]
David P. Williamson; David B. Shmoys, The Design of Approximation Algorithms, Cambridge University Press, 2011, 頁は著者公開の電子版(2011)のもの:§5.1(問題の定義)p. 107、Theorem 5.3 p. 107、第 5 章の章末の注 p. 139、Theorem 6.9 p. 145、緩和の値との比較 pp. 145–147、Theorems 6.10・6.11 p. 147、第 6 章の章末の注 p. 159
[2]
Jeff Erickson, Algorithms, 1st paperback edition, Independently published, 2019, §12.12(Subset Sum の NP 困難性)pp. 402–404、§12.13(MaxCut)p. 406

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する