Lovász local lemma
組合せ論の分野には良い性質を満たすものの存在を確率論を用いて証明する確率論的手法(probabilistic method)が知られています. 本記事では確率論的手法における非常に有名なLovász local lemmaについて紹介します.
謝辞
本記事においてU.M.さんに有益なコメントを頂いたことをこの場を借りて御礼申し上げます。
確率論的手法
確率論的手法は主に, 良い性質を満たすものの存在性を証明するために使われます. 具体的には, ランダムに構成したものが所望の性質を正の確率で満たすことが言えれば存在性を示せたことになります. $n\in\mathbb{N}$に対し$[n]=\{1,\dots,n\}$とします.
例1. グラフの最大カット
無向グラフ$G=(V,E)$の頂点部分集合$S,T\subseteq V$に対し, $E(S,T)$を$S$-$T$間のカット辺の集合とします. すなわち$E(S,T)=\{\{u,v\}\in E:u\in S,t\in T\}$. 集合$E(S,V\setminus S)$を, 頂点集合$S$に対するカット辺と呼びます.
与えられた無向グラフ$G=(V,E)$に対して$|E(S,V\setminus S)|$を最大にする$S$を求める計算問題を最大カット問題といいます. この問題はNP困難であることが知られており, 多項式時間で最適解を得ることは不可能であると広く信じられています.
明らかに任意の$S$に対し$|E(S,V\setminus S)|\leq |E|$ですが, 一方で$|E(S,V\setminus S)|\geq |E|/2$を満たす$S$は必ず存在します.
任意のグラフ$G=(V,E)$に対し, $|E(S,V\setminus S)|\geq 0.5|E|$を満たす$S\subseteq V$が存在する.
各頂点に対し, 確率1/2で表が出るコインを投げ, 表が出た頂点の集合を$S$とする. このとき
\begin{align*}
\mathrm{E}[|E(S,V\setminus S)|]=\sum_{e\in E}\Pr[e\in E(S,V\setminus S)] = \frac{|E|}{2}.
\end{align*}
期待値以上のサイズを持つカットは必ず存在するので, 主張は示された.
命題1はタイトで, 任意の$\epsilon>0$とどのような$S$に対しても$|E(S,V\setminus S)|\leq (0.5+\epsilon)|E|$となるグラフが存在します. 例えば, 偶数$n$に対し完全グラフ$K_n$は$|S|=n/2$の時に$|E(S,V\setminus S)$が最大になり, そのときは$|E(S,V\setminus S)|=n^2/4$となります. 一方で$|E|=\binom{n}{2}=n(n-1)/2$なので, $n$を十分大きくとればよいです.
$\mathsf{P}\neq \mathsf{NP}$の仮定の下では最大カット問題は最適解を多項式時間で計算できませんが, 上の議論より最適解の半分以上の個数の辺を持つカットはコインを投げるだけで簡単に得ることができます. これは$0.5$近似解と呼ばれてます. 実はそれよりも良い約$0.878$近似解を多項式時間で得る方法が知られています.
例2. ラムゼー数の下界
非常に有名な次の問題を考えてみます:
6人集まったとき, 知り合い同士の3人かもしくは互いに知らない3人が必ず存在する.
この問題はグラフで表現すると, 以下のようになります:
頂点数$6$の完全グラフ$K_6$の各辺を赤もしくは青で塗り分ける. このとき, 赤い$K_3$(全ての辺が赤で塗られている$K_3$)もしくは青い$K_3$が必ず存在する.
この問題を一般化し次の値$R(k,l)$を考えます:
次の性質を満たす最小の$n$を$R(k,l)$とし, ラムゼー数と呼ぶ:
頂点数$n$の完全グラフ$K_n$の各辺を赤もしくは青で塗り分ける. このとき, 赤い$K_k$もしくは青い$K_l$が必ず存在する.
数学者のFrank P. Ramsey(1903-1930)は$R(k,l)$が有限であることを証明しました (ラムゼーの定理). ラムゼー数$R(k,l)$は組合せ論において非常に多くの研究がなされているほど有名なトピックです.
ここでは, 確率論的手法を使ってラムゼー数の下界を簡単に導出することができることを紹介します.
$n,k\in\mathbb{N}$が
$$\binom{n}{k}2^{1-\binom{k}{2}}<1$$
を満たすならば, $R(k,k)>n$.
条件を満たす$k,n$を固定し, 頂点数$n$の完全グラフ$K_n$を考える. $K_n$の各辺を一様ランダムに赤または青で塗り分ける. $X$を同色の$K_k$(赤い$K_k$または青い$K_k$)の個数とする. 固定した一つの$K_k$が同色になる確率は$2^{1-\binom{k}{2}}$であり, $K_n$の中から一つの$K_k$を選ぶのは$\binom{n}{k}$通りあるので, $k,n$の条件より
$\mathrm{E}[X]=\binom{n}{k}2^{1-\binom{k}{2}}<1$.
期待値$\mathrm{E}[X]<1$より必ず$\Pr[X=0]>0$となる. この確率が正ということは, 上手く塗り分けることによって同色の$K_k$が存在しないようにできる. これは$R(k,k)>n$を意味する.
例3. ハイパーグラフの2彩色
有限集合$V$に対し$\binom{V}{k}=\{S\subseteq V:|S|=k\}$とします. $E\subseteq \binom{V}{2}$に対して組$G=(V,E)$をグラフと呼びますが, これを一般化して頂点部分集合族$F\subseteq 2^V$に対して$H=(V,F)$をハイパーグラフと呼び, 特に$F\subseteq \binom{V}{k}$ならば$H=(V,F)$を$k$一様ハイパーグラフと呼びます. $V$の元を頂点, $F$の元をハイパー辺と呼びます. 特に, $2$一様ハイパーグラフはグラフと一致します.
次にハイパーグラフの彩色の概念を導入します.
ハイパーグラフ$H=(V,F)$に対し, $c:V\to [k]$が次の条件を満たすとき, $H$の$k$-彩色という. 全てのハイパー辺$e\in F$に対し, ある2頂点$a,b\in e$が存在し$c(a)\neq c(b)$.
次の結果は, 一様ハイパーグラフに対し$2$-彩色の存在性を主張します.
$H=(V,E)$を$k$一様ハイパーグラフとする. $|E|<2^{k-1}$ならば$H$は$2$-彩色を持つ.
$k$一様ハイパーグラフ$H=(V,F)$を考える.
$c:V\to[2]$をランダムな関数とする. すなわち, 各頂点$v\in V$に対し$c(v)=1$または$c(v)=2$を確率$1/2$で決める. ある固定したハイパー辺$e\in F$が全て同じ色で塗られる(すなわち, ある$c\in[2]$が存在して全ての$a\in e$で$c(a)=c$)確率は$2^{1-k}$となる. 同じ色で塗られたハイパー辺の個数を$X$とすると, その期待値は$\mathrm{E}[X]=|E|2^{1-k}$. $|E|<2^{k-1}$のとき, この期待値は$1$未満なので, 特に$\Pr[X=0]>0$となる. すなわち$H$は2-彩色を持つ.
Lovász local lemma
Lovász local lemmaを紹介します. Lovász local lemmaは, $n$個の事象$A_1,\dots,A_n$に対し$\Pr[\overline{A_1}\land \dots\land \overline{A_n}]$の下界を与える結果です. つまり, $n$個の起こって欲しくない事象が一つも起こらない確率を評価しています. もし$A_1,\dots,A_n$が独立な事象ならば当然この確率は$\prod_{i\in[n]} \Pr[\overline{A_i}]$となりますが, Lovász local lemmaでは必ずしも独立とは限らない事象$A_1,\dots,A_n$を扱います.
主張を述べるために幾つか用語を準備します.
有限集合$V$に対し, $(V)_2=\{(i,j):i,j\in V,i\neq j\}$とし, その部分集合$E\subseteq (V)_2$に対し組$G=(V,E)$を有向グラフという. グラフ$G=(V,E)$の頂点$i\in V$に対し, $N^+(v)=\{j\in V:(i,j)\in E\}$とする.
グラフ理論の文脈では有向グラフを考えるときは自己ループや多重辺を考えることもありますが, ここではそれらのないものを有向グラフとしています.
事象$E$が事象$A_1,\ldots,A_n$と相互に独立(mutually independent)であるとは, 任意の$S\subseteq [n]$に対し
$$\Pr\left[E\land \bigwedge_{i\in S}A_i\right]=\Pr[E]\cdot \Pr\left[\bigwedge_{i\in S}A_i\right]$$
が成り立つことをいう.
複数の事象$A_1,\dots,A_n$の独立性を表す従属グラフを考えます.
事象$A_1,\ldots,A_n$に対し, 以下を満たす有向グラフ$G=(V,E)$を従属グラフという.
- $V=[n]$.
- 各頂点$i$に対し, 事象$A_i$は事象$(A_j)_{j\in V\setminus (\{i\}\cup N^+(i))}$と相互に独立.
一般に従属グラフは$A_1,\dots,A_n$から一意に定まるわけではないことに注意してください.
事象$A_1,\dots,A_n$が独立ならば, 空グラフ$G=([n],\emptyset)$は従属グラフになる.
どんな事象$A_1,\dots,A_n$に対しても, 完全グラフ$([n],([n])_2)$は従属グラフになる.
事象$A_1,\dots,A_n$の従属グラフを一つ任意に選び$G$とする. さらに, ある$(x_1,\dots,x_n)\in[0,1]^n$が存在して次を満たすとする: 全ての$i\in[n]$に対し$\Pr[A_i]\leq x_i\prod_{j\in N^+(i)}(1-x_i)$. このとき,
$$\Pr\left[\bigwedge_{i\in [n]}\overline{A_i}\right]\geq \prod_{i\in[n]}(1-x_i).$$
事象$A_1,\dots,A_n$を考える. 各$A_i$は$A_1,\dots,A_n$のうち高々$d$個を除いた全てと相互に独立とする. 更に, $\Pr[A_i]\leq p$とする. このとき, $\mathrm{e}p(d+1)<1$ならば$\Pr\left[\bigwedge_{i\in[n]}\overline{A_i}\right]>0$. ここで$\mathrm{e}=2.7182\dots$はネイピア数.
条件を満たす$A_1,\dots,A_n$に対してはある従属グラフ$G$が存在して全ての頂点の出次数を高々$d$にできる. すなわち各$i\in[v]$で$|N^+(i)|\leq d$. $x_i=1/(d+1)$とおき, $p<\frac{1}{\mathrm{e}(d+1)}$とすれば定理4の条件を満たす. 実際,
$$p< \frac{1}{\mathrm{e}(d+1)} \leq \frac{1}{d+1}\prod_{j\in N^+(i)}\left(1-\frac{1}{d+1}\right)$$
である(ここで, 任意の$d\geq1$に対し$(1-1/(d+1))^d>1/\mathrm{e}$が成り立つことを使った).
このとき, 定理4より
$$\Pr\left[\bigwedge_{i\in[n]}\overline{A_i}\right]\geq \left(1-\frac{1}{d+1}\right)^n>0.$$
以降では, Lovász local lemmaを適用して色んな結果を証明していきます. カギとなるのは, 従属グラフをどう構成するか, そのために事象$A_1,\dots,A_n$をどう定義するかです. 基本的には定理4系を適用します. そのためには, できるだけ出次数の小さい従属グラフを考えていきます.
適用例1. ハイパーグラフの彩色
例3で考えたハイパーグラフの彩色を考えます. ハイパーグラフ$H=(V,F)$の頂点$v\in V$の次数$\deg(v)$を, $v$を含むハイパー辺の個数で定める. すなわち$\deg(v)=|\{e\in F:v\in e\}|$とする. $H$の最大次数を$\max_{v\in V}\deg(v)$で定義する.
最大次数が高々$d$の$k$一様ハイパーグラフ$H=(V,F)$を考える. $d<(2^{k-1}/\mathrm{e}-1)/k$ならば$H$は2彩色を持つ.
$c:V\to[2]$をランダムな関数とする. 各ハイパー辺$e\in F$に対し, $e$が$c$の下で単色になる(すなわち, ある$i\in[2]$が存在し全ての頂点$a\in e$が$c(a)=i$となる)事象$A_e$とする. このとき, $c$が2-彩色になることと$\bigwedge_{e\in F}\overline{A_e}$が成り立つことは等価であるため, $\Pr[\bigwedge_{e\in F}\overline{A_e}]>0$を示せば良い.
ハイパー辺$e\in F$を一つ固定する. もし別の辺$f\in F$が$e\cap f=\emptyset$ならば, 二つの事象$A_e$と$A_f$は独立である. 同様に, $f_1,\dots,f_m\in F$が全て$e\cap f_i=\emptyset$となるならば, $A_e$と$A_{f_1},\dots,A_{f_m}$は相互に独立である.
そこで, $e$と共通部分を持つ辺の個数を考える. $H$は$k$一様だから$e$はちょうど$k$個の頂点を持ち, 最大次数の条件から各頂点$v\in e$は高々$d$個の辺に含まれている. すなわち, $e$と共通部分を持つ辺は高々$kd$個となり, $A_e$は$kd$個を除いた全ての事象と相互に独立となる.
更に, どの辺に対しても$A_e= 2^{1-k}$である. 次数$d$の条件より$\mathrm{e}2^{1-k}(kd+1)<1$なので, 定理4系より所望の主張$\Pr[\bigwedge_{e\in F}\overline{A_e}]>0$が得られる.
適用例2. CSPの充足可能解
CSP(constraint satisfaction problem)とは, 大雑把にいうと離散値をとる変数に関する連立方程式を解けという問題です. ある種のCSPは必ず方程式の解を持つということをLovász local lemmaを使って証明することができます.
$\Sigma$を有限集合, $x_1,\dots,x_n$を変数, $C_1,\dots,C_m$を関数とし, 各$C_i$は$C_i:\Sigma^n\to\{\mathsf{true},\mathsf{false}\}$であって, インデックス集合$S_i\subseteq [n]$に対し$C_i$は$(x_j)_{j\in S_i}$に依存するものとします. CSPは, 全ての$i\in[m]$に対し$C_i(x)=\mathsf{true}$となるような$x\in\Sigma^n$が存在するかどうかを判定する計算問題です. そのような$x$が存在するとき, その$x$を$(C_1,\dots,C_m)$の充足解と呼び, 特に充足解を持つとき$(C_1,\dots,C_m)$は充足可能という.
例えば, $n=5$, $\Sigma=\{0,1\}$, $S_1=\{1,2,3\}$, $S_2=\{2,3,4\}$, $S_3=\{3,4,5\}$とし, 各$C_i$を方程式
$$\sum_{j\in S_i} x_j = 1 \bmod 2$$
とします. つまり, $(x_1,\dots,x_n)\in\{0,1\}^n$がこの方程式を満たすならば$C_i(x_1,\dots,x_n)=\mathsf{true}$で, そうでないなら$C_i(x_1,\dots,x_n)=\mathsf{false}$です. これは$x_1=\cdots=x_5=1$は充足解の一つです.
各$S_i$に対し, $S_i\cap S_j\neq\emptyset$となる$j$が高々$d$個あるとする. また, $x=(x_1,\dots,x_n)$のそれぞれに独立に$\Sigma$から一様ランダムに選んだ値を代入したとき, $\Pr[C_i(x)=\mathsf{false}]\leq p$であるとする. このとき, もし$\mathrm{e}p(d+1)<1$ならば, $(C_1,\dots,C_m)$は充足可能である.
各$x_j$にそれぞれ独立に$\Sigma$から一様ランダムに値を代入して$x=(x_1,\dots,x_n)$とする. $x$が充足解になる確率を考える. 各$i\in[m]$に対し, $A_i$を$C_i(x)=\mathsf{false}$となる事象とする. このとき, $x$が充足解になる確率は$\Pr\left[\bigwedge_{i\in[n]}\overline{A_i}\right]$と等しい.
事象$A_i$は, $S_i\cap S_j=\emptyset$なる$j$に対する$A_j$と独立である(代入するランダム割り当ての変数が互いに素であるため). 従って定理4系より, $\Pr\left[\bigwedge_{i\in[n]}\overline{A_i}\right]>0$である.
このように, 各$C_i$によって定められる局所的な制約から充足可能解の存在性という大域的な情報を得られるのがLovász "local" lemmaたる所以です.
CSPは計算量理論で最も重要な問題の一つとされるSAT(satisfiability)を特殊ケースとして含み, 一般に充足可能か否かの判定はNP完全です. 定理6では, 変数の被り具合が小さい場合は必ず充足可能であることを示しました. それでは充足解を求める効率的なアルゴリズムは存在するのでしょうか？ 理論計算機科学ではこのトピックはAlgorithmic Lovász local lemmaと呼ばれており, 近年の理論計算機科学のトップの国際会議STOCやFOCSにはこのトピックの論文がいくつも採択されています.
まとめ
本記事では組合せ論における確率論的手法を簡潔に導入し, その後Lovász local lemmaを解説しました. その応用としてCSPの充足可能性などを議論し, 近年の理論計算機科学ではAlgorithmic Lovász local lemmaに関する研究がなされているなど, Lovász local lemmaの影響は組合せ論にとどまらないことをみてきました. このトピックに興味のある方は参考文献[1]を読んでみてください.