埋め込みクリーク問題
概要
グラフ$G=(V,E)$に対し, 頂点部分集合$C\subseteq V$は$\binom{C}{2}\subseteq E$を満たすときクリークと呼び, 特に頂点数$k$のクリークを$k$-クリークと呼びます. 入力として与えられたグラフ$G=(V,E)$のクリークのうち頂点数最大のものを求める問題を最大クリーク問題と呼び, 古典的なNP困難問題の一つです.
埋め込みクリーク問題 (Planted Clique Problem)とは, 最大クリーク問題の平均時計算量解析の文脈で現れる問題で, 端的に言うとランダムな場所に大きいクリーク$C$を埋め込まれたランダムグラフが入力として与えられたときに, クリーク$C$を求めよという問題です. この問題の計算量的困難性は, 高次元統計学など幅広い分野の問題の計算量的下界を導くのみならず, 暗号学的プリミティブの構成(一方向性関数)などにも応用されています. 暗号学的プリミティブの安全性は素因数分解やLearning with Errorやその他の代数的な問題の困難性に依拠していますが, 一方で最大クリークといった組み合わせ的な問題の困難性に依拠したプリミティブ(特に公開鍵暗号方式)の構成は知られておらず, 重要な研究テーマと認識されています.
背景
最大クリーク問題はNP完全なので最悪時の意味では広くその困難性が信じられています. 実はそれだけではなく, 平均時計算量の意味でも最大クリークは多項式時間で解けないであろうと予想されています.
具体的にはグラフ$G$がErdős–Rényiグラフ である時, すなわち$G=G(n,1/2)$のときに最大クリークを見つけられるかを議論します.
ランダムグラフ$G(n,1/2)$は確率$1-o(1)$で最大クリークのサイズが$\approx 2\log_2 n$となることが知られています. 一方, 適当な単一頂点からスタートして一つずつ頂点を追加していくと極大クリークが得られますが, このようにして得られる極大クリークの頂点数は高確率で$\approx \log_2 n$となることが知られています (ここでの「高確率」とは$G(n,1/2)$の選択に関する確率). したがって単純な貪欲法は$G(n,1/2)$上では最大クリーク問題を近似率$1/2$で解くことになりますが, 実は近似率$0.501$達成する多項式時間アルゴリズムは知られていません.
ランダムグラフ$G(n,1/2)$はサイズ$2\log_2 n$のクリークを持つ. これにサイズ$k\gg\log n$のクリークを埋め込まれたときにそれを探したい.
定義
$G(n,1/2)$上の最大クリーク問題では本質的に, サイズ$2\log_2 n$のクリークが含まれていることがわかっているグラフが与えられたときにそのクリークを見つけ出せるかが問われていました. そこで, より一般にサイズ$k \gg \log n$のクリークが含まれていることがわかっているグラフが与えられたときにその$k$-クリークを見つけ出せるかという問題を考えます.
パラメータ$n,k\in \mathbb{N}$ (ただし$k\le n$) に対し, $\PC(n,k)$を以下の手続きによって定まる分布とする.
- $G = G(n,1/2)$を生成する. 頂点集合を$V(G)=[n]$とする.
- 一様ランダムな$k$-頂点部分集合$C\sim \binom{[n]}{k}$を選ぶ.
- グラフ$G’=\left([n],E(G)\cup \binom{C}{2}\right)$を出力する.
また, 上記における頂点部分集合$C$を埋め込まれたクリーク (planted clique)と呼ぶ.
LWE問題と同様に, 埋め込みクリーク問題においても探索や判定などの問題設定が考えられています.
埋め込みクリーク探索問題
探索問題では埋め込まれたクリークを復元せよという問題を考えます.
パラメータ$n,k\in \mathbb{N}$ (ただし$k\le n$) に対し, 分布$\PC(n,k)$に従って選ばれたグラフ$G’$を入力として受け取り, 埋め込まれたクリーク$C$を出力せよという問題を埋め込みクリーク探索問題という.
アルゴリズム$\mathcal{A}$は,
\[\begin{align*} \Pr_{\substack{G'\sim \PC(n,k)\\ C:\text{ planted clique of $G'$}}}\qty[ \mathcal{A}(G') = C ] \ge \gamma \end{align*}\]を満たすとき, 埋め込みクリーク探索問題を成功確率$\gamma$で解くという (もしくは単に成功確率$\gamma$で埋め込みクリークを探すという).
ここでは考えるランダムグラフの辺密度を$1/2$に固定していますが, より一般に$p \in [0,1]$でパラメタライズされた設定も考えることができます.
埋め込みクリーク判定問題
判定問題ではクリークが埋め込まれたグラフ$G’$をErdős-Rényiグラフ$G(n,1/2)$と識別する問題を考えます.
クリークを埋め込まれたランダムグラフとただのランダムグラフを識別したい.
もう少し詳しくいうと, 埋め込みクリーク判定問題ではアルゴリズムの入力として一つのグラフが与えられます. ただしこのグラフは$G\sim \calG(n,1/2)$ (Erdős-Rényiグラフ$G(n,1/2)$の分布)もしくは$G\sim \PC(n,k)$のいずれかです. このとき, アルゴリズムの入力はどちらの分布から生成されたかを当てる問題が判定問題です.
出力値が0または1のアルゴリズム$\mathcal{A}$は
\[\begin{align*} \left| \Pr_{G\sim \PC(n,k)}[\mathcal{A}(G) = 1] - \Pr_{G\sim \mathcal{G}(n,1/2)}[\mathcal{A}(G) = 1] \right| \ge \gamma \end{align*}\]を満たすとき, 埋め込みクリーク判定問題をアドバンテージ$\gamma$で解くという.