埋め込みクリーク問題

与えられたグラフ$G=(V,E)$に含まれる最大クリークを求めよという問題はKarp's 21 Complete Problemの一つであり, おそらく最も有名なNP困難な問題の一つとして知られています. 本記事ではこの問題の平均時困難性について考えます. すなわち, 与えられたグラフがErdos-Renyiランダムグラフ$G(n,1/2)$のときの最大クリーク(を見つける問題)について紹介し, 関連問題として埋め込みクリーク問題を紹介します.

ランダムグラフ上の最大クリーク問題

Erdős--Rényiグラフ$G(n,1/2)$を考えます. このグラフは$n$個の頂点からなり, 各頂点のペアは独立に確率$1/2$で辺を持ちます. 言い換えれば, $n$頂点の頂点ラベル付きグラフの中から一様ランダムに選ばれたグラフが$G(n,1/2)$です. このように, 入力がランダムに生成された時に問題が効率的に解けるかどうかを議論する枠組みを平均時計算量といいます.

最大クリーク問題に戻りましょう. Erdős--Rényiグラフ$G(n,1/2)$は高確率でおよそサイズ$2\log_2 n$のクリークを持つことが示せます. ここでは厳密な証明はしませんが, なぜ$2\log_2 n$という値が出るかについて, $k$-クリークの個数の期待値を使って簡単に説明します. グラフ$G(n,1/2)$に含まれる$k$-クリークの個数を$X_k$とします. $X_k>0$ならば最大クリークのサイズは$k$以上であり, $X_k=0$ならば$k$未満となります. 頂点部分集合$S\subseteq[n]$に対し, $S$がクリークであるかどうかのindicatorを$X_S$とします. すなわち$S$が$G(n,1/2)$内でクリークになっているならば$X_S=1$, そうでなければ$X_S=0$です. 固定した$S$に対して$X_S=1$となる確率は$(1/2)^{\binom{|S|}{2}}$です. さて, $X_k = \sum_{S\subseteq[n],|S|=k} X_S$ と書けます. 期待値の線形性より, $X_k$の期待値は
\begin{align*}
\mathbb{E}[X_k] &= \sum_{S\subseteq[n],|S|=k} \Pr[X_S=1] \\
&= \binom{n}{k}\cdot 2^{-\binom{k}{2}} \\
&\approx \frac{n^k}{k!} 2^{-k^2/2} \\
&\approx 2^{-k\log_2 n - k^2/2} \\
&\approx 2^{-k(\log_2 n - k/2)}
\end{align*}
となります. 途中で突然$k!$が消えたのは, $k!=2^{(1-o(1))\cdot k\log k}$は$2^{-\binom{k}{2}}$に比べて無視できるほど小さいからです. $k\gg \log_2 n$ならば指数部が負となり$X_k$の期待値は非常に$0$に近い値となります. $k\ll \log_2 n$ならば期待値は非常に大きい値となるので, $G(n,1/2)$は$k$-クリークを含むだろうことがわかります. 前半の議論(非存在性)はMarkovの不等式, 後半の議論(存在性)はChebyshevの不等式を使うと厳密な議論にできます. 詳しく知りたい方はこちらの記事を参照してください.

すなわち, 入力が$G(n,1/2)$だと最大クリークのサイズはおよそ$2\log_2 n$であることがわかります. では, この$2\log_2 n$-クリークを見つけられるでしょうか?

成功確率の枠組み

そもそも「ランダムグラフ上で問題を解く」とはどういうことなのでしょうか?

最悪時計算量の枠組みでは, 「全ての入力に対して正しい答えを出力する」効率的なアルゴリズムの構成が焦点になっていました. 一方で平均時計算量では「全ての入力に対して」という部分を「多くの入力に対して」に緩和した枠組みを考えます. 本当はerrorless/error-proneの二つの概念があるのですが, ここではerror-proneの枠組みを考えます.

定義 (成功確率)

決定的アルゴリズム$A$は以下を満たすとき, 成功確率$\gamma$で$G(n,1/2)$上で最大クリークを解くという:
\begin{align*}
\Pr_{G \sim G(n,1/2)} [ A(G) \text{ outputs a maximum clique in }G]\ge \gamma.
\end{align*}

$A$が乱択アルゴリズムのとき, 上の確率において入力$G\sim G(n,1/2)$および$A$の内部のランダムネスについての確率をとることで成功確率を定義する.

直感的に言えば成功確率とはアルゴリズム$A$が解く(固定サイズの)入力の割合を意味します. 平均時計算量の理論では, 効率的(例えば多項式時間)なアルゴリズムの中で最大の成功確率$\gamma$をもつものが研究の対象となります.

入力によって解けるか解けないかが決まるので, 乱択アルゴリズムのように
「繰り返して成功確率を増幅させる」ことはできない.

例えば, 成功確率$\gamma=1$のアルゴリズムは最悪時の意味において最大クリーク問題を解くことを意味します. これはNP困難なので, $\gamma=1$を満たす多項式時間アルゴリズムは存在しないと広く信じられています. 従って$\gamma<1$の範囲で考えます. この記事では確率$1-o(1)$を「高確率」と呼ぶことにします(注1).

(注1). 「高確率」という言葉は専門用語として扱われることが多いです. ランダムグラフの文脈では漸近的に確率$1$で成り立つことを「a.a.s. (asymptotically almost surely)」「w.h.p. (with high probability)」と言うことがあります. また, 乱択アルゴリズムの文脈では, 何らかの定数$c>0$が存在して確率$1-n^{-c}$で成り立つことを「高確率」ということもあります.

上の定義では誤った答えを出力しうるものの常に多項式時間で終了するアルゴリズムを考えていました. このようにアルゴリズムの「誤りうる」という性質をerror-proneと言います. 一方で, 常に正しい答えを出力するが入力によっては指数時間かかりうるという性質をerrorlessといいます. 乱択アルゴリズムの文脈で例えるとラスヴェガス法か, モンテカルロ法かという話です. 

最悪時と平均時のギャップ

さて, $G(n,1/2)$上での最大クリーク問題に話を戻しましょう. 証明はしませんが, $G(n,1/2)$は確率$1-n^{-\Omega(\log n)}$で最大クリークのサイズが高々$2.01\log_2 n$であることが証明できます. 従って, サイズ$2.01\log_2 n$以下の頂点部分集合$S \subseteq [n]$ を全て列挙し, クリークをなした$S$の中で最大のものを出力すると, $n^{O(\log n)}$時間で成功確率$1-n^{-\Omega(\log n)}$で$G(n,1/2)$上で最大クリークを解けます.

最悪時の世界では最大クリーク問題はETH(強指数時間仮説)の下では$2^{\Omega(n)}$時間かかると予想されていますが, 平均時の世界では単純なbrute-forceを考えれば$n^{O(\log n)}$時間で高確率で解くことができます.

貪欲法

最大クリーク問題に対する最も単純なアプローチが貪欲法です. 何でも良いので極大クリークを一つ選び, 出力するというアルゴリズムです. 例えばクリークに追加できる頂点のうち, インデックスが一番若い頂点を選んで追加するというルールを考えてみましょう.

定理 (Karp, 1976, informal).

入力$G(n,1/2)$上の貪欲法で得られる極大クリークを$S$とすると, 確率$1-o(1)$で$|S| = (1\pm o(1))\log_2 n$を満たす.

すなわち, 貪欲法は"ほぼ2近似"アルゴリズムであるといえます. 最悪時の世界では, 任意の小さな定数$c>0$に対して最大クリークを多項式時間で$n^{1-c}$近似するのはNP困難であることが知られているので, この定理もまた最悪時と平均時の世界のギャップを意味します.

証明(の概要).
貪欲法の$t$回目の反復で得られる頂点部分集合を$S_t$とします. すなわち, $S_0=\emptyset$であり, $S_{t+1}$は$S_t\cup \{u\}$がクリークになるような頂点$u$のうち最もインデックスが若いものとします (例えば一番最初に追加される頂点は必然的に最もインデックスの若い$v_1$になります). $S_t$の要素数は$t$なので, 貪欲法が終了したときのステップ数$t$の上下界を求めればよいことになります.

この「若い頂点を優先する」貪欲法は, 頂点を$v_1,\dots,v_n$の順に見ていき初めて追加できる頂点を見つけたらそれを追加するというように実装することができます. この実装では, 例えば時刻$t$で頂点$v_i$が追加されたとすると, その反復までにアルゴリズムは以降の頂点$v_{i+1},\dots,v_n$を見ていないことになります (もちろんこれは実装依存ですが, $v_{i+1},\dots,v_n$を見ないように実装したものと同じ出力を得るので, 見ていないということを仮定できます). すなわち, この反復までの挙動は誘導部分グラフ$G[\{v_1,\dots,v_i\}]$にのみ依存するのであって, $v_{i+1},\dots,v_n$に接続する辺の情報とは独立です. ですので, 頂点$v_{i+1}$を見たとき, その時初めて辺$\{v_{i+1},v_j\}$ ($j=1,\dots,n\}$) に関する入力の情報をサンプルする (つまり, 入力を生成→アルゴリズムの解析, ではなく, アルゴリズムの反復に応じて入力を徐々に生成していく) という確率過程によってアルゴリズムの振る舞いを解析ができます.

時刻$t$における反復において$S_t$の要素数は$t$であり, $S_t$の全ての頂点と隣接している頂点が新たに$S_{t+1}$に加わるわけですが, 固定した頂点$v_j$が追加される確率は$(1/2)^t$です. 従って, 任意の定数$c>0$に対し$t\ge (1+c)\log_2 n$ならば, $v_j \in [n]$に関するunion boundより一つも頂点が追加されないので, $t \le (1+c)\log_2 n$を得ます. 逆に, $t<(1-c)\log_2 n$ならばこの確率は$n^{-1+c}$となり, 追加できる頂点の個数の期待値はおよそ$n^c$で非常に大きいので, そのような頂点は高確率で存在することになります.

$v_j$は$S_t$の全ての頂点と隣接していればクリークに追加できる.

(証明終)

衝撃的なことに, 本質的に貪欲法より良い多項式時間アルゴリズムはいまだに知られていません (それどころか存在しないと予想されています). 具体的には, 以下の主張が正しいかどうかは非常に重要な未解決問題です.

ある定数$\varepsilon>0$と多項式時間アルゴリズムが存在して, $G(n,1/2)$上で$(1+\varepsilon)\log_2 n$-クリークを確率$2/3$で見つける.

埋め込みクリーク問題

Erdős--Rényiグラフ$G(n,1/2)$上の最大クリーク問題の変種として, $k$-クリークが埋め込まれたランダムグラフから$k$-クリークを復元する問題を考えます. 具体的には, 入力として次の操作によって得られるランダムグラフ$G(n,k,1/2)$が与えられます:

1. Erdős–Rényiグラフ $G(n,1/2)$を生成する, ランダムに$k$個の頂点$v_1,\dots,v_k$を選び, $C=\{v_1,\dots,v_k\}$とする.
2. 各$1\leq i<j\leq k$に対して辺$\{v_i,v_j\}$を追加して$C$をクリークにする (元々$\{v_i,v_j\}$が辺をなす場合は追加しない).

ここで埋め込むクリークサイズ$k$は$k \gg \log n$とします. Erdős--Rényiグラフ$G(n,1/2)$はサイズが$O(\log n)$のクリークを持つので, 直感的にはサイズ$k$のクリークをランダムに埋め込むと一意になる気がします.

最大クリークのときと同様に, アルゴリズムの成功確率を以下のように定義します.

定義 (成功確率)

決定的アルゴリズム$A$は以下を満たすとき, $G(n,k,1/2)$上で成功確率$\gamma$で埋め込みクリーク問題を復元するという:
\begin{align*}
\Pr_{G \sim G(n,k,1/2)} [ A(G,k) \text{ outputs the planted $k$-clique $C$ in }G]\ge \gamma.
\end{align*}

ここでは, 簡単のため, アルゴリズム$A$はクリークサイズ$k$知っていると仮定する.

$A$が乱択アルゴリズムのとき, 上の確率において入力$G\sim G(n,k,1/2)$および$A$の内部のランダムネスについての確率をとることで成功確率を定義する.

情報理論と計算量理論のギャップ

例えば$k=2$の場合はただの辺が埋め込まれただけなので, ランダムな辺を出力するしかできないので情報理論的に成功確率の上回は$O(1/n^2)$となります. 一方で任意の定数$c>0$に対し, $k\ge (2+c)\log_2 n$のとき, $G(n,k,1/2)$は確率$1-2kn 2^{-k/2}$で$k$クリークを一つだけ含むことが初等的な数え上げで示すことができます. このとき, 全探索によって高確率で埋め込んだクリークを復元できます.

実は, $G(n,1/2,k)$上でも$k\ge (2+c)\log_2 n$であれば ($k=n^{0.1}$とかであっても), $n^{O(\log n)}$時間で$k$-クリークを確率$1-o(1)$で解くことができます. 一方で$k \le 2\log_2 n$のときはErdős--Rényiグラフ$G(n,1/2)$は$2\log_2 n$クリークを持つので情報理論的に埋め込まれた$k$-クリーク$C$を復元することはできません.

命題.

任意の定数$c > 0$および$k\ge (2+c)\log_2 n$に対し, $G(n,1/2,k)$上で成功確率$1-o(1)$で埋め込みクリーク問題を解く$n^{O(\log n)}$時間アルゴリズムが存在する. 

証明.

アルゴリズムは非常にシンプルです: サイズ$2\log_2 n$の頂点部分集合$S \subseteq V$を列挙し, もしも$S$が$G(n,1/2,k)$においてクリークをなすならば貪欲法によって極大クリークを一つ選び, そのサイズが$k$と等しいならばその極大クリークを出力する. 最終的にサイズ$k$のクリークが見つからなかったら特別な記号$\bot$ (見つからなかった, を意味する)を出力する.

列挙した各$S$に対して一つの極大クリークしか考えないので計算時間は$n^{O(\log n)}$です. あとはこれで「取りこぼしがない」ことを証明する必要があります. $C$を埋め込まれたクリークとします. 列挙したときにある$S \subseteq C
$に対して, $C$以外の頂点が貪欲法で追加され得ないことを示せばよいです. フォーマルに言うと, ある$S\subseteq C,|S|=2\log_2 n$が存在して, $C$の外側の頂点$v$であって$\Gamma(v) \supseteq S$を満たすものがないことを示せば, $V\setminus C$の頂点が貪欲法で追加され得ないため必ず極大クリークは$C$になります.

こうなるような$S$の存在性を示したい.

埋め込む位置$C$と$V\setminus C$の間の辺は全て独立なコイントスによって決まります. そこで固定した$C$で条件つけたときに所望の$S\subseteq C$が高確率で存在することが言い, その後に$C \sim \binom{[n]}{k}$に関する期待値をとれば$G(n,1/2,k)$上の確率を抑えたことになります.

固定した$C\subseteq [n]$に対し, $S\subseteq V$を$C$内からインデックスの若い$2\log_2 n$個の頂点からなる集合とします. $C$は固定されているため$S$もまた固定されています. 従って, 各$v \in V \setminus C$について$v$が$S$の全ての頂点に隣接している確率は$(1/2)^{2\log_2 n}\le n^{-2}$です (これは$S$が固定されているため, $S$の情報と辺の有無の情報が独立だから成り立つ). $v$についてのunion boundより, 確率$1-O(n^{-2})$で$\Gamma(v)\supseteq S$を満たす$v \in V\setminus C$は存在しません. すなわち, この$S$の構成は高確率で所望の性質を満たします. なお, この議論は$\log_2 n$の係数が$1$より真に大きければ同様に適用できます.

以上より, $G(n,1/2,k)$において, 埋め込んだクリーク$C$の中からインデックスの若い順に$2\log_2 n$個の頂点集合を$S$とすれば, $S$を含む極大クリークは$C$のみになりますので, 確かに列挙するアルゴリズムは埋め込みクリークを解きます. (証明終)

ここまでで単純な列挙によって$n^{O(\log n)}$時間で埋め込みクリーク問題は$k\ge 2.01\log_2 n$ならば高確率で解けることを確認し, $k\le 2\log_2 n$では情報論的に解けないことを見てきました. これは$k=2\log_2 n$が情報理論的に解けるかどうかの境界になっていると解釈できます. では, 同様の範囲の$k$で埋め込みクリーク問題を多項式時間で解けるでしょうか?

結論から言うと$k\ge \sqrt{n}$であれば確率$1-o(1)$で埋め込みクリーク問題は多項式時間で解けることが知られている[Alon, Krivelevich, Sudakov, '98]のですが, $k = o(\sqrt{n})$に対して多項式時間で解けるかどうかは30年来の未解決問題で, 実はある$c>0$に対して$k=n^{1/2-c}$に対して多項式時間で確率$2/3$で埋め込みクリーク問題を解く多項式時間アルゴリズムは存在しないのではないかと予想されています (埋め込みクリーク予想).

ここではAlonらの結果より少し弱い, $k\ge 10\sqrt{n\log n}$のときに埋め込みクリーク問題を解くアルゴリズム[Kučera, 95]を紹介します.

命題.

$k\ge 10\sqrt{n\log n}$のとき, $G(n,1/2,k)$上の埋め込みクリーク問題を高確率で解く多項式時間アルゴリズムが存在する.

証明 (概要).

アルゴリズムは「次数の大きい順に頂点を$k$個出力する」です. 埋め込まれたクリーク$C$に属する頂点は, クリークの分だけ次数が大きくなるはずであり, $k\ge 10\sqrt{n\log n}$ならばその差が有意であるという議論をします.

頂点$v \not\in C$の次数の周辺分布は二項分布$\mathrm{Bin}(n,1/2)$なので, Hoeffdingの不等式および$v$に関するunion boundより
\begin{align*}
\Pr[\exists v\not\in C,\deg(v) > n/2 + \sqrt{n\log n}] \le n\cdot \exp(-2\log n) \le n^{-1}
\end{align*}

を得ます. 一方, $v\in C$の次数の周辺分布は$k+\mathrm{Bin}(n-k,1/2)$なので, 同様にHoeffdingの不等式より, 任意の$t>0$に対し

\begin{align*}
\Pr\left[\exists v\in C,\deg(v) < \frac{n-k}{2}+k-t\right] \le n\exp\left(-\frac{2t^2}{n}\right).
\end{align*}

特に$t=4\sqrt{n\log n}$を代入すると, 確率$1-o(1)$で全ての$v\in C$は$\deg(v) \ge \frac{n}{2} + \sqrt{n\log n}$を満たします. 従って$k\ge 10\sqrt{n\log n}$のとき確かに次数を見ることで$C$が復元できます. (証明終)

Appendix. 埋め込みクリークの一意性

ランダムグラフ$G(n,k,1/2)$は埋め込まれたものが一つあるので, $k$クリークを一つ以上部分グラフとして含みます. ここでは$k\ge (2+c)\log_2 n$の場合は高確率で$k$クリークが一つであることを証明します.

この主張は直感的には自明に思えます. Erdős--Rényiグラフ$G(n,1/2)$の最大クリークは$2\log_2 n$なので, それより大きい$k$-クリークを埋め込むと確かに埋め込まれたクリーク以外に$k$-クリークは登場しなさそうです. ところが, $k$-クリークを埋め込むことによって非自明に大きいクリークが発生しうる懸念をケアしなければなりません.

$G(n,1/2,k)$における他のクリークのサイズはどのくらいになるのでしょうか? 埋め込まれたクリークを表す頂点部分集合を$C$とします. 任意の頂点$v \not \in C$は$C$内におおよそ$k/2$個の隣接点を持ちます.

これは, $v$と$C$の間の辺は独立に確率$1/2$で生起するので, $\Gamma(v)$を$v$の隣接点の頂点集合とすると, $|\Gamma(v) \cap C|$の周辺分布は$\mathrm{Bin}(k,1/2)$になり, これにHoeffdingの不等式を適用することでわかります (より詳しくいうと, 確率$1-n^{-100}$で, 全ての頂点$v$に対し$|\Gamma(v) \cap C| \le k/2 + 100\sqrt{k\log n}$がいえる.)

また, $\{v\} \cup \Gamma(v)$は$G(n,k,1/2)$内でクリークをなすので, $C$以外にも$k/2$-クリークを持つことがわかります. 実は$C$以外のクリークのサイズは全て$k/2 + O(\sqrt{k\log n}) \approx (1+o(1))k/2$以下になります.

この議論に基づくと, $k\ge 100\log_2 n$に対して$k$-クリークの一意性が証明できます (特に, Hoeffdingの不等式でネイピア数が出てくるのでlogの底に関して慎重にならなければなりません). $k\ge (2+c)\log_2 n$に対して一意性を示すにはもう少し丁寧な議論が必要です.

命題 [Theorem 4, Jerrum '92]. 任意の$k$に対して, $G(n,k,1/2)$が二つ以上の$k$クリークを含む確率は高々$2kn2^{-k/2}$である.

証明 (概要).

$V=[n]$を頂点集合, $C\subseteq V$を埋め込まれた$k$クリークとします. $C$とは別の$k$-クリーク$C' \neq C$の個数を$X$とし, その期待値を考えます. すなわち
\begin{align*}
\mathbb{E} = \sum_{C'\in \binom{V}{k},C'\neq C} \Pr[C'\text{ is a $k$-clique}]
\end{align*}

を上から抑えます. 各$t=0,1,\dots,k-1$に対し, $|C'\cap C|=t$なる$C'$を列挙して$t$に関する和を考えると

期待値$\mathbb{E}[X]$は
\begin{align*}
\mathbb{E}[X] &= \sum_{t=0}^{k-1} \binom{k}{t}\binom{n-k}{k-t}\cdot 2^{-\binom{k}{2} + \binom{t}{2}} \\
&\le \sum_{t=0}^{k-1} \left(kn 2^{-k/2}\right)^{k-t} \\
&\le kn 2^{-k/2} \cdot \sum_{t=0}^\infty (1/2)^t \\
&\le 2kn 2^{-k/2}
\end{align*}
を得ます.