グラフの直径と支配集合

グラフの頂点$v$の隣接点集合を$N(v)$とし, $S\subseteq V$に対して $N(S)=\bigcup_{s\in S} N(s)$ と定めます. グラフ$G=(V,E)$の頂点部分集合 $D\subseteq V$ は, $D\cup N(D)=V$ となるとき支配集合 (dominating set) であると言います. 言い換えると, 任意の$v\in V\setminus D$は$D$の何らかの頂点に隣接しているとき, $D$は支配集合となります.

グラフ$G$が入力として与えられたとき, $G$がサイズ$k$の支配集合を持つかどうかを判定する問題は($k$も入力で与えられるとき)NP-完全となり, $k$をパラメタとみなしたときはW[2]-困難となります. 全探索だと $O(n^{k+1})$時間で解けますが, $k=2$の時は$O(n^\omega)$時間で解けます ($\omega\leq 2.373$は行列積の計算時間の指数).

グラフ$G$がサイズ2以下の支配集合を持たないと仮定しましょう. すると, 任意の二頂点$v_1,v_2\in V$に対して, $v_1$と$v_2$のどちらとも隣接しない頂点$w\in V\setminus \{v_1,v_2\}$ が存在することになります. では, $G$の補グラフ $\bar{G}$ を考えてみましょう. すると前述の条件は, 任意の$v_1,v_2\in V$に対してある$w\in V\setminus \{v_1,v_2\}$が存在して$w$は$v_1$と$v_2$のどちらとも隣接している, というものになります. 言い換えると任意の二頂点間には長さ2のパスがあるということを意味するため, 直径が2以下である, ということになります. したがって補グラフの直径が2以下かどうかを判定すればよく, これは隣接行列の二乗を計算すれば終わるので$O(n^{\omega})$時間で判定できるわけです. 逆に, $G$の直径が$2$以下の場合はその補グラフがサイズ$2$以下の支配集合を持たないことも言えます. この観察をまとめると,

$G$はサイズ$2$以下の支配集合を持たない iff 補グラフ$\bar{G}$の直径は2以下.

この記事の本質的な部分は以上となるのですが, 折角なのでこの事実を使って次の定理を証明しようと思います.

定理1.
任意の$d\geq 3$に対して, $d^2$頂点を持つ$(d^2-d-1)$-正則グラフはサイズ$2$の支配集合を持つ.

証明.
背理法で示します. $d^2$頂点の$(d^2-d-1)$-正則グラフでサイズ$2$以下の支配集合を持たないものが存在すると仮定し, そのグラフを$G$とします. $G$の補グラフ$\bar{G}$は $d^2$頂点を持つ$d$-正則グラフとなり, 上記の事実により$\bar{G}$の直径は$2$となります (直径=1 iff 完全グラフなので, 直径=2になる).

ところが, $d$-正則グラフで頂点数=$d^2$かつ直径=2となるものは長さ4の閉路以外に存在しない[1]ため, $d\geq 3$に矛盾 (証明終).

文献[1]の結果の証明はこちらの記事のように, 隣接行列の固有値の多重度などを考えれば得られます. 文献[1]のページ数は4ページしかなく読むのにそれほど時間がかからないと思うので興味のある方はぜひ読んでみてください.

定理2. 
任意の$d\not\in\{2,3,7,57\}$に対して, 任意の$d^2+1$頂点 $(d^2-d)$-正則グラフはサイズ$2$の支配集合を持つ.

証明.
定理1の証明とほぼ同じです. $d^2+1$頂点, $(d^2-d)$-正則でかつサイズ$2$の支配集合を持たないグラフ$G$が存在するならば, その補グラフ $\bar{G}$は$d^2+1$頂点$d$-正則グラフでしかも直径=2となります. このようなグラフは Moore graph 以外に存在しないので, $d\in \{2,3,7,57\}$ となるので矛盾です (証明終).


[1] P. Erdős, S. Fajtlowicz, A. J. Hoffman. Maximum degree in graphs of diameter 2, Networks, Vol. 10, Issue. 1, 1980.

Schwartz-Zippelの脱乱択化 ⇒ 回路計算量下界

計算量理論の主要な分野の一つに回路計算量というものがあります. これはなぜメジャーなのでしょう？

判定問題を解くアルゴリズムを実行しているチューリング機械は回路によって表現できます. 実行時間 $T$ のアルゴリズムはサイズ $O(T\log T)$ の回路によって模倣することが出来ます. 具体的にはチューリング機械の「1ステップ模倣回路」を構築し, これを $T$ 段積み重ねれば所望の回路が得られます. いわば, 回路は計算を模倣するモデルであるため, その研究は計算の本質を掴む良いアプローチになるというわけです.

さて, 多項式時間アルゴリズムの動作は多項式サイズの回路によって模倣できる (専門用語で言うとP $\subseteq $ P/poly が成り立つ) ので, 対偶をとると「多項式サイズ回路で解けない問題は多項式アルゴリズムで解けない」ことが言えます.

多項式時間アルゴリズムで解ける判定問題のクラスはPと呼ばれますが, 多項式サイズの回路で解ける判定問題のクラスは P/poly と呼ばれます. もう少しちゃんと言うと, 判定問題とは言語 $L \subseteq \{0,1\}^*$ のことであり, インスタンス $x\in\{0,1\}^*$ に対して $x\in L$ か否かが問われます. 言語 $L$ は以下の条件を満たすとき, P/poly に属すると言います:

(条件) ある回路族 $\{C_n\}_{n\in\mathbb{N}}$ が存在して, 各$n$に対して$C_n$の素子数は$n$の多項式で上から抑えられており, さらに任意の$x\in\{0,1\}^*$ に対して $C_{|x|}(x)=1$ iff $x\in L$ が成り立つ. ここで $|x|$ は$x$の文字数.

冒頭に述べたように, (チューリング機械上の)多項式時間アルゴリズムは多項式サイズの回路によって模倣できるため, PはP/poly に含まれます. この包含関係はstrictで, 以下に示すように, 実はP/polyは計算不可能な判定問題も含んでいます:

例: ビット列 $x\in \{0,1\}^n$ とチューリング機械が一対一対応することが知られています (チューリング機械全体は加算無限個). そこで, 自然数$n$に対してその二進表記に対応するチューリング機械を$M_n$と表すことにします. さて, 言語 $L$ として $L=\{1^n: M_n$ は任意の入力に対して停止する $\}$ と定めます. このとき $L\in $P/polyが成り立ちます. 実際, $C_n$として, $x=1^n$かつ$M_n$が停止するならば $C_n(x)=1$, そうでないならば $0$ を出力する回路とすると, $C_n$のサイズは $O(n)$ です ($M_n$が停止するかどうかは神様が知っていて, その神様が各$n$に対して$C_n$を設計してくれた, と思ってください. クラスP/polyでは, 回路族の存在性を要請しているのであってその回路族がチューリング機械によって構成できかどうかは要請していません！). すると $C_n$ は $L$を解くので, $L\in $P/polyとなります.


回路計算量理論では, 色んな問題に対してその問題を解く回路のサイズはどれくらいなのかを研究しています. 具体的には問題クラスの回路下界や, 回路のタイプを制限 (単調回路など) したときの回路下界などが研究されています.

前置きが長くなりましたが, 本記事では脱乱択化と回路計算量下界の関係について概説します.

 ZEROPの脱乱択化

与えられた多変数多項式 $P(x_1,\ldots,x_n)$ が恒等的に $0$ かどうかを判定する問題をZEROP と呼びます. ここで入力は以下の例のように算術回路で与えられるものとします.

この問題はランダムな値を代入したときに$0$になるかどうかを確認し, これを繰り返すことにより, with high probability で解くことができます (例えばこの記事で紹介されているSchwartz-Zippelの補題を参照してください). 実は, ZEROPはクラスPに属するか否かは未解決です (計算量理論ではpseudorandom generatorが存在し即ちP=BPPであると信じられているため, ZEROPはクラスPに属するだろうと信じられています).

Schwartz-Zippelの補題が脱乱択化できればZEROPも脱乱択化できてハッピーなのですが, ZEROPの脱乱択化に関して以下の結果が知られています:

定理1 [Kabanets Impagliazzo, 2003]
以下の三つの主張のうち, 少なくとも一つは偽である.
(1). ZEROPはクラスPに属する.
(2). 01行列のパーマネントは多項式サイズの算術回路で解ける.
(3). NEXP $\subseteq$ P/poly.

それぞれの主張を見ていきます. (1)は上記の通りで, ZEROPが脱乱択化出来るということを意味します. (2)は読んだままです. 多項式サイズの算術回路で解けるというのはP/polyの算術回路版のような意味です. 普通の回路では各ゲートに and か or が記されていますが算術回路では + , -, × のいずれかが記されており, 出力ゲートからは期待した値が出てくるようなものです (そのため, 計算途中のビット長などは気にしません). (3)のNEXPというのはNPの指数時間verです. NPは非決定的チューリング機械で多項式時間で解ける問題のクラスですが, NEXPは非決定的チューリング機械で指数時間 (i.e., $2^{\mathrm{poly}(n)}$時間) で解ける問題のクラスです. なので, P$\subseteq$NPと同様にEXP$\subseteq$NEXPが成り立ちますが, EXP$\neq$NEXPかどうかは未解決です (P$\neq$NPならばEXP$\neq$NEXPが直ちに従います).

つまり, 定理1より, ZEROPが脱乱択化できたら, either パーマネントは多項式サイズの算術回路で計算できない or NEXPというクラスは多項式サイズの回路で解けないことが分かるため, 回路計算量の下界が得られたことになります. これが脱乱択化によって示される回路計算量下界ということになります.

定理1の証明を全て網羅しようとすると, pseudorandom generator, 対話証明 (クラスMAとか), IP=PSPACE, 戸田の定理, 非決定性の時間階層定理, easy witness lemmaといった多くの前提知識が必要となりとても大変です. なので本記事では計算量クラスには出来るだけ触れず, なぜパーマネントやZEROPが登場するかについて重きをおいた議論について概説したいと思います.

以下の補題を考えます. 専門用語が多いので, 下に概説を付け加えました.

補題1.
NEXP $\subseteq$ P/poly ならば, NEXP=EXP.

補題2 (非決定性チューリング機械の時間階層定理).
NEXP ≠ NP.

補題3 (Meyerの定理).
$\Sigma_2$を,  $\exists x\forall y: \phi(x,y)$  の判定問題として表せる問題のクラスとする ($\phi$は論理式). このとき, $\mathrm{EXP}\subseteq \mathrm{P}/\mathrm{poly}$ ならば $\mathrm{EXP}=\Sigma_2$.

補題4 (戸田の定理の特殊ケース).
$\Sigma_2\subseteq \mathrm{P}^{\mathrm{perm}}$.

補題1は, easy witness lemma (IKW02) と呼ばれる面白い結果から従うのですが, その証明をしようとするとpseudorandom generator, クラスMAなどの説明から始めなくてはならずとても大変なので本記事ではそこまでしません. 補題2は時間階層定理の非決定性verです. 証明は決定性の時と同じようにはいかず, 少し難しいです.　補題3における$\Sigma_2$とは多項式時間階層の一つです. 例えばNPの問題は多項式長の証拠が存在するような問題なので, $\exists x:\phi(x)$ という形で書けるのですが, ここに出てくる量化子を交互に繰り返した問題を考えることで多項式時間階層  (PH: polynomial hierarchy) が構成されます. もう少しちゃんと言うと, 量化子が有限回交互に繰り返された形で書ける問題のクラスをPHと呼びます. ちなみに, coNPという計算量クラスは $\forall x: \phi(x)$ の形で書けるものであり, $\exists$と$\forall$を入れ替えたものとして解釈できるため, coNP$\subseteq$ PHです. $\mathrm{P}^{\mathrm{perm}}$とは, 行列のパーマネントを計算するオラクルを用いて多項式時間で判定できる問題のクラスです (厳密には, 行列$A$とインデックス$i$を受け取り, $A$のパーマネントの第iビット目が0か1かを判定するというオラクルを持ったチューリング機械で多項式時間で判定出来る問題のクラスです). 戸田の定理は PH$\subseteq \mathrm{P}^{\mathrm{perm}}$ を主張しており, 戸田 誠之助先生によって1981年に発表されました. この定理は計算量理論において非常に重要な定理として知られています. とても面白い解説がこちらにあるので, 興味のある方はぜひ目を通してみてください. 上に述べた補題はどれも重要な結果なので補題というよりそれ自体が定理になるような結果です. 本記事では補題1~4を認めて定理1の証明を行います.

定理1の証明.
主張(1)~(3)が成り立つと仮定するとNEXP=NPになってしまい補題2に反する, という流れで証明します. まず

主張(1),(2)⇒$\mathrm{P}^{\mathrm{perm}}\subseteq \mathrm{NP}$

を示します. まず, $\mathrm{P}^{\mathrm{perm}}$ に属する問題Xに対して多項式長の証拠があることを言います. この問題Xはパーマネントをオラクルとした多項式時間アルゴリズムで解くことが出来るので, オラクル呼び出しの部分をパーマネントを計算する多項式サイズの回路に置き換えることができます (c.f. 主張(2)). より正確には, 主張(2)より行列のパーマネント計算は多項式サイズの回路の族$\{C_n\}$で解くことが出来るため, この回路を表現するビット文字列をwitnessとして与え, そのwitnessで得られた回路をオラクル呼び出しの部分に置き換えることで問題Xを解きます. このとき, NPに属することをちゃんと証明するためには, この記事にあるように, witnessで与えられた回路が本当にパーマネントを計算しているかどうかをチェックする必要があります. このチェックする部分で主張(1)を用います.

今, 算術回路族$\{C_i\}$を持っていて ($i\leq \mathrm{poly}(n)$), 各$C_i$が本当にサイズ$i\times i$の行列のパーマネントを計算するかどうかをチェックしたいとしましょう. 明らかに$1\times 1$行列のパーマネント計算の回路のチェックは簡単です. さて, $C_1,\ldots,C_t$がそれぞれ正しいとしたとき, $C_{t+1}$の正当性のチェックを行うアルゴリズムを考えます. $A$を$(t+1)\times (t+1)$行列として, その$1$行目と$j$列目だけを除去して得られる$t\times t$行列を$A_{1,j}$とします (下図参照).

$\mathrm{perm}(M)$ で行列 $M$ のパーマネントを表すとします. すると, 行列式の展開と同じ要領で, $\mathrm{perm}(A)=\sum_{j=1}^{t+1} \mathrm{perm}(A_{1,j})$ が成り立つことが分かります. 今, 行列$A$を引数として持つ多項式

$P(A):=\sum_{j=1}^{t+1}C_t(A_{1,j})-C_{t+1}(A)$ ..........(＊)

を考えます. 各回路$C_t,C_{t+1}$は算術回路として表現されているので多項式になっていることに注意してください. 帰納法の仮定より, $C_t(A_{1,j})=\mathrm{perm}(A_{1,j})$なので, $C_{t+1}$がパーマネントを正しく計算する iff $P(A)$は恒等的に$0$. したがって$(t+1)^2$変数多項式 $P$ に対して ZEROP を解くことによって, witnessとして与えられた回路族 $\{C_t\}$ が正しくパーマネントを計算するかどうかをチェックすることが出来るので, $\mathrm{P}^{\mathrm{perm}} \subseteq \mathrm{NP}$ が成り立ちます.

EXP$\subseteq$NEXPなので, 主張(3)より, EXP$\subseteq$P/polyです. したがって

主張(3)⇒$\mathrm{NEXP}=\mathrm{EXP}$.

主張(3) & 補題3 ⇒$\mathrm{EXP}\subseteq \Sigma_2$.

補題4 & 主張(＊)⇒$\Sigma_2 \subseteq \mathrm{P}^{\mathrm{perm}} \subseteq \mathrm{NP}$.

これらを組み合わせると, 主張(1)~(3) ⇒ $\mathrm{NEXP}\subseteq \mathrm{NP}$ となり, 補題2と矛盾が生じます. よって主張(1)~(3)が全て真になることはありません.

参考文献

S. Arora and B. Barak, Computational Complexity: A Modern Approach, Cambridge University Press.

閉路検出問題の計算複雑性

グラフ $H$ を固定し, $H$-Detection という問題を考えます. この問題はグラフ $G$ が入力で与えられたときに $G$ が $H$ を部分グラフとして含むかどうかを判定する問題です.

例えば, $H$ が長さ$|V(G)|$ の閉路だとするとこれはハミルトン閉路問題になるのでNP-困難です. 一方で $H$ が辺数 $|V(G)|/2$ のマッチングならば完全マッチングを含むかどうかの判定問題になるので, 多項式時間で解けます. それでは, どのような$H$に対して $H$-Detection は多項式時間で解けるのでしょうか？

この話はグラフアルゴリズムの分野でよく研究されている分野であり, 結論から言うと未解決なのですが, $H$のサイズをパラメータとしたときに$H$-Detectionは「木幅がunbounded ならばW[1]-困難である」という予想が有ります[1] (逆に木幅がboundedならばcolor codingでFPT時間で解けます). 本記事では $H$を様々な長さの閉路としたときどのような結果が知られているかについてまとめていきます. 基本的に$n=|V(G)|$, $m=|E(G)|$ とします.

$k$-cycle

一般の$k$に対しては color coding というアルゴリズムによって, $2^{O(k)}\cdot n^{\omega}$時間で解けます ($n\times n$の行列積が$O(n^{\omega})$ 時間でできるとします. 2019年6月1日現在では, $\omega\approx 2.373$ です).

$k$が定数だとしましょう. 実は, 現状では$k$の偶奇によって計算量が変わります. $k$が奇数のときはこれまで知られている最速のアルゴリズムは $O(n^{\omega})$ 時間です. 例えば $k=3$ の場合は隣接行列の3乗を計算して体格成分だけを見れば良いですね. 一方で$k$が偶数のときは, $O(n^2)$で解くアルゴリズムが知られています[2]. 例えば$k=4$の時は以下の単純なアルゴリズムで四角形を見つけることができます. ただし $N(u)$は頂点$u$の隣接頂点の集合とします.

このアルゴリズムでは配列 $\mathrm{T}[i][j]$ は二頂点$ij$間の長さ2のパスをカウントしていて, もし$\mathrm{T}[i][j]\geq 2$ なる$ij$が見つかったらその瞬間に四角形が有ると判定してアルゴリズムを終了します. 配列$\mathrm{T}$の各要素は高々2回しかアクセスされないはず (2回アクセスしたらその瞬間にアルゴリズムはtrueを返して終了する) なので, 計算時間は$O(n^2)$になるわけです.

また, 辺数$m$に関しては近年にもう少し早いアルゴリズムが知られていたり[2]して, 自分が把握する限りをまとめるとこんな感じになります.

ハミルトン閉路

ハミルトン閉路はTSPで使うDPを考えると$O(2^n n^2)$時間で解くことができるのですが, それでは$O(1.99^n)$時間で解けるのでしょうか？ (乱択を許せば)できることが知られています[4]. アルゴリズムではまず, 入力のグラフ$G$を使ってある多変数多項式 $P$ を構成し, $P$が恒等的に$0$かどうかを乱択で判定するというものです. ここで構成する多項式$P$は, 「$P$が恒等的に0 iff グラフがハミルトン閉路を持つ」という性質を満たすようなものを上手く構成します. したがって多項式が恒等的に0かどうかの判定が出来る決定的アルゴリズムがあればハミルトン閉路の検出も決定的に出来るようになります. CyganらによるFPT algorithmの本[5]の10.4.2に分かりやすく解説されているので興味のある方はどうぞ.

[1]. M. Grohe, The complexity of homomorphism and constraint satisfaction problems seen from the other side, J. ACM, 2007.

[2]. R. Yuster and U. Zwick, Finding even cycles even faster, SIAM J. Discrete Math, (1997).

[3] S. Dahlgaard, M. B. T. Knudsen, M. Stöckel, Finding even cycles faster via capped k-walks, In Proc. of STOC2017.

[4]. A Björklund, Determinant sums for undirected Hamiltonicity, SIAM J. COMPUT., 2014.

[5]. M. Cygan, F. V. Fomin, Ł. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, S. Saurabh, Parameterized Algorithms, Springer Publishing Company, 2015.