数理解析研究所講究録
第 1849 巻 2013 年 8-118

森および連結全域部分グラフの乱択近似数え上げ
Randomized Approximate Counting of Forests and ConnectedSpanning Subgraphs
三原勇治

山内由紀子

来嶋秀治

山下雅史

Yuji Mihara

Yukiko Yamauchi

Shuji Kijima

Masafumi Yamashita

九州大学
Kyushu University

1

はじめに組合せ構造の近似数え上げと (一様) ランダム生
成の間には，自己帰着性 (self-reducibility) を通じて密接に関係することが知られている．基本的な組

2

準備

2.1

マルコフ連鎖の定常分布

有限の状態空間$\Omega$と遷移確率行列 $P$. によって定まみ合わせ構造の一つである全域木のランダム生成にる，マルコフ連鎖を考える．マルコフ連鎖の定常分は [2]を初め，様々な多項式時間アルゴリズムが知ら 布とは，$\pi P=\pi$を満たすような$\Omega$上の確率分布$\pi$れている．一方，全域木の一般化にあたる森や連結である．マルコフ連鎖が以下の二つの性質を満たす
全域部分グラフの数え上げ問題は#$P$完全であることき，エルゴード的であると呼び，唯一の定常分布とが知られ，多項式時間近似アルゴリズムの存在性に収束することが知られている．

は重要な未解決問題である．1. 既約，すなわち任意の状態
マルコフ連鎖モンテカルロ (MCMC) 法は，森および連結全域部分グラフの多項式時間一様ランダム$P^{t}(x, y)>0$となる$t$$x,$ $y\in\Omega$が存在する．

生成法として有望である．MCMC の計算効率性につ

2. 非周期，すなわち任意の状態いて，設計したマルコフ連鎖が定常分布に十分収束$gcd\{t|P^{t}(x, x)>0\}=1$するまでに必要な遷移回数 (mixing time:混交時間)
schendorf[2]が解析の焦点となる．Fehrenbach とは最大公約数のことである．

$R\ddot{u}$について$x\in\Omega$についてである．ここで $gcd$

マルコフ連鎖モンテカルロ (MCMC) 法は，サンは全域木上のマルコフ連鎖に対し，多品種流を用いプリングにマルコフ連鎖を用いる手法である．一般た解析により，混交時間が頂点数の多項式で抑えら 的なサンプリング方法は，まずサンプリングを行いhendorf の解 たい目標分布を定常分布として持ち，かつそれに収析では，Cordovil と Moreira [1] が示した全域木に 束するようなマルコフ連鎖を設計する．次に，ある対する bases-cobases グラフの連結性が重要な役割 初期状態から遷移を開始し，十分遷移させた後の状れることを示した．Fehrenbach と$R\ddot{u}\mathfrak{X}$を果たしている．本研究では，森および連結全域部態を出力することでサンプルを得る．

分グラフに対して Cordovil と Moreira [1] の結果を拡張する．この結果を用いて，辺数が全域木よりも1 つ少ない森上のマルコフ連鎖に対し，[2] と同様の解析を行い，混交時間が頂点数の多項式で抑えられることを示す．

2.2

マルコフ連鎖の混交時間

混交時間 (mixing time) とは，マルコフ連鎖が定常分布に収束するまでに必要な遷移回数である．ま9ず，定常分布との距離の指標として時刻 における全変動距離 (total variation distance) を$t$と定義する．但し は，マルコフ連鎖 $M$ の定常分布とする．この混雑度を用いて，混交時間に対して次のような上界が得られる．
$\pi$$d_{TV}(P^{t}, \pi):=\max_{x\in\Omega}\frac{1}{2}\sum_{y\in\Omega}|P^{t}(x, y)-\pi(y)|$定理 1[3]と定義する．この全変動距離を用いて，任意のに対して混交時間$\tau(\epsilon)$$\Omega$$\epsilon>0$

は以下のように定義される．

$\tau(\epsilon):=\min\{t|\forall t’\geq t, d_{TV}(〆, \pi)\leq\epsilon\}$

2.3

Bases-cobases グラフを有限集合とし，$E$ との組持つとき，$E$$\mathcal{F}\subseteq 2^{E}$$\mathcal{F}$上のマルコフ連鎖が(1) エルゴード的で， を定常分布に持つ
$\pi$

(2)

$\forall x,$(3)$\forall x\in\Omega,$$y\in\Omega,$$\pi(x)P(x, y)=\pi(y)P(y, x)$$P(x, x) \geq\frac{1}{2}$を満たす時，その混交時間$\tau(\epsilon)$と任意の多品種流 $F$が以下の 3 つの性質を に対し，をマトロイドと呼ぶ．

$(E, \mathcal{F})$$\tau(\epsilon)\leq\rho(F)(\log\hat{\pi}^{-1}+\log\epsilon^{-1})$

1.

$\emptyset\in \mathcal{F}$2.

$F_{1}\subseteq F_{2}\in \mathcal{F}\Rightarrow F_{1}\in \mathcal{F}$が成立する．但し，$\hat{\pi}=\min_{x\in\Omega}\pi(x)$3.

$F_{1},$$F_{2}\in F,$:$|F_{1}|<|F_{2}|\Rightarrow\exists e\in F_{2}\backslash F_{1}$$F_{1}\cup\{e\}\in \mathcal{F}$$E$
マトロイド $M=(E, \mathcal{F})$ に対し，を台集合，3である．

森/連結全域部分グラフに対するbases-cobases グラフの連結性$\mathcal{F}$を独立集合族，各を独立集合と呼ぶ．また，
Cordovil と Moreira [1] の拡張を与える．グラフ$E$ がサイズの排反な二つの$G=(V, E)$ に対して，極大な独立集合を基と呼ぶ．
$G$ 中のサイズマトロイド $M$ に対し，その台集合 $E$ がある 2 つの 森の和である時，の森全体を基とす$M$ をブロツクるブロックマトロイドが存在する．
排反な基の和集合となっているとき，マトロイドと呼ぶ．ブロックマトロイド $M$ に対し，$M$ をサイズの森$M$ の基 $B$も $M$ の基であるよう 定理 2 任意の $r\in N$ に対し，で，その補基$M$ の basesを基とするブロックマトロイドとする．
なものを頂点とし，要素がちょうど一つ異なる基の組 $(B, B’)$ を辺とするグラフを $M$ の bases-cobases cobases グラフにおいて，相補的な基に対応する任意の頂点対は長さ の道で結ばれている．
グラフと呼ぶ．
$F\in \mathcal{F}$

$r$

$r$

$r$

$E\backslash B$$r$$E$ があるサイズの排反な二つの連結全同様に，域部分グラフの和である時， 中のサイズ の連結全域部分グラフ全体を基とするブロックマトロイドが存在する．
$r$

2.4

多品種流による混交時間の解析

上のマルコフ連鎖 $M$ に対し， を $M$ の状態遷移図における状態 から状態 への全ての単純有$\Omega$$\mathcal{P}_{xy}$$x$

向道の集合とする．

$x,$ $y\in\Omega$$\Re_{0}^{+}$

$G$

$r$

$y$

$f_{xy}:P_{xy}arrow$
に対し，$M$ をサイズ定理 3 任意の $r\in N$ に対し，$r$の連結を $\sum_{p\in \mathcal{P}_{xy}}f_{xy}(p)=1$ を満たす関数とした時， 全域部分グラフを基とするブロックマトロイドとす$F=\{f_{xy};x, y\in\Omega\}$$\rho(F)$を多品種流ど呼ぶ． の混雑度
$F$を

$M$ の bases-cobases グラフにおいて，相補的なる．
基に対応する任意の頂点対は長さ の道で結ばれて$r$いる．
$\rho(F)=P(v,w)>0\max\frac{1}{\pi(v)P(v,w)}\sum_{p_{xy}\ni(v,w)}\pi(x)\pi(y)f_{xy}(p_{xy})|p_{xy}$104

辺数 $n-2$ の森上のマルコフ連鎖 に対し，$\sum_{p\in P_{XY}}f_{XY}^{A}(p)=1$を定義し，$\mathcal{P}_{XY}arrow\Re_{0}^{+}$

に対する混交時間の解析を満たす関数$f_{XY}(p)=f_{XY}^{\emptyset}(p)$は $H$ に対してり，$H_{A}$

際にでも$X\cup A$$X\backslash Y$とと$Y\cup A$$Y\backslash X$

は排反な森である．実が共に森であるような任意のを定義する際は，まの辺との各連結成分において，$A\subset E\backslash (X\cup Y)$$H_{A}$の辺を縮約してできるグラフであ$A$に対して$f_{XY}^{A}$

ムに選ぶ:

2. $Y=(X\backslash \{e\})\cup\{f\}$ とする．
で $Y$ , 確率1 で $X$ とする．

$A$に対して$f_{XY}^{A}$を定義する．
に関して再帰的にを定義する．$\ell=1$ の場合，
$X$ から $Y$ への遷移
$P(X, Y)>0$ である．この場合，$B_{0}=X,$だけからなる道 $p=(B_{i})_{0\leq i\leq 1}$ (すなわち，$f_{XY}^{A}(p)=1$$B_{1}=Y)$ に対してとし，それ以外の道に対しては $f_{XY}^{A}(p’)=0$ とする．
$X\cup A$ と $Y\cup A$ が共に森$\frac{1}{2}|X\oplus Y|<P$の場合，$f_{XY}^{A}$$\ell$$\frac{1}{2}$$Y\backslash X$$X\backslash Y$

1. $e\in X$ と $f\in E$ をそれぞれ独立かつ一様ランダ が排反な二つの全域木を構成するの場合，次状態を確率とする．
$H_{A}$

ず$Y\in\Omega$:

また $H_{A}=(V, X\cup Y)/((X\cap Y)\cup A)$ とする．

無向グラフ $G=(V, E)$ に対し，$|V|=n,$ $|E|=m$$\Omega=\{F\subseteq E|F$ は森 $, |F|=n-2\}$ を状態とする．
空間とするマルコフ連鎖 $M$ は，現状態を $X\in\Omega$ とした時，以下のように次状態を決定する．

3. (a)$f_{XY}^{A}$$p’\in \mathcal{P}_{XY}\backslash p$(b)$Y\not\in\Omega$の場合，次状態を $X$ とする．

定理 4 マルコフ連鎖 $M$ は一様分布を唯一の定常分布にもち，かつそれに収束する．

であるような任意の $A\subset E\backslash (X\cup Y)$ に対し，既に$f_{XY}^{A}$は定義されていると仮定する．

$\frac{1}{2}|X\oplus Y|=l$

また混交時間に関して以下の定理を得る．
定理 5 任意の $\epsilon\in(0,1)$ に対し，グラフ $G=(V, E)$に対してに対するマルコフ連鎖 $M$ の混交時間$\tau(\epsilon)$のを $H_{A}$ 上の孤立点以外の頂点の場合を考える．
$D$ を次数が最小次数とし，$d_{\min}$$d_{\min}$である頂点の集合とする．各 $v\in D$ に対し，以下の (1), (2) を満たす
ような $X’,$ $Y’\in\Omega$ と $A’\subset E$ の組 $(X\prime, Y’, A’)$ の集
合 $S$。を選ぶ．

(1) $\frac{1}{2}|X’\oplus Y’|=P-1$$\tau(\epsilon)\leq 2n^{4}m(n\ln m+\ln\epsilon^{-1})$$n:=|V|,$ $m:=|E|$ である．
が成立する．ただし，マルコフ連鎖 $M$ の混交時間を解析するために，多品種流を構成する．すなわち，任意の $X,$ $Y\in\Omega$ に対(2) $X’\cup(A\cup A’),$ $Y’\cup(A\cup A’)$ は共に森

再帰の仮定より，任意の $(X\prime, Y’, A’)\in$ s。に対し，,$f_{XY}^{A\cup A’}$は既に定義されている．さらに，$f_{XY}^{A\cup A’},(p’)>$

して，関数 $f_{XY}$ : x $Yarrow\Re$ まを定義する．ここで， である各道 $p’\in P_{X’Y’}$ に対し，それを拡張してを作り，p$X$ と $Y$ を重ね合わせ，共通の辺を縮約してできるグ$0$$\mathcal{P}$$\in \mathcal{P}XY$$H$ 上では
ラフ $H=(V, X\cup Y)/(X\cap Y)$ を考える．

は排反な森であり，$\ell:=|X\backslash Y|=|Y\backslash X|$ とすである．したがって，$X\backslash Y$と$f_{XY}^{A}(p):= \frac{1}{|D|}\frac{1}{|S_{v}|}f_{XY}^{A\cup A’},(p’)$$|X\backslash Y|=|Y\backslash X|$$Y\backslash X$$H$ 中のサイズの森を基とするブロックマトると，$X$ロイドが存在する． から $Y$ への道の内，このブロツクマトロイドの bases-cobases グラフ上を移動するような道 に対してのみ $f_{XY}(p)>0$ とする．すとする．

$\ell$$p$

なわち，$p=(B_{i})_{0\leq i\leq\ell}$$H$ 上でのて，$B_{i}$とすると，任意の$i$に対しの補グラフも森である道に対して$f_{XY}(p)>0$ とする．

$X’,$ $Y’\in\Omega$ と $A’\subset E$ の$v\in D$ に対して，次に，の道の道から組の集合 。の選び方と，$S$.とに接続している辺の集合を$X$ と $Y$ は辺数 $n-2$ の森であるので，握手補する．
$d_{\min}=1,2,3$ のそれぞれ
題より $d_{\min}<4$ である．の作り方を示$C_{v}$$v$の場合を考える．

Casel. $d_{\min}=1$ の場合， $=\{a\}$ とし，一般性を$C=\{d\in$失うことなく $a\in X$ とする．このとき，$Y|X\cup\{d\}$ は閉路をもたない (全域木)とする．各$C$$X\cup A$ と多品種流の構成法について以下述べる．
$Y\cup A$ が共に森であるような任意の$A\subset E\backslash (X\cup Y)$$\mathcal{P}_{XY}$$\mathcal{P}_{X’Y’}$$\neq$。

$\}$

11
に対し，$d\in C$$X_{v}^{d}=(X\backslash \{a\})\cup\{d\},$より，る．と仮定を満たす．さらに，である．この場合，$\frac{1}{2}|X_{v}^{d}\oplus Y_{。}^{d}|=\ell-1$$X_{v}^{d},$$X_{v}^{d}\cup\{a\}$

$S$

。

る．道から
$\mathcal{P}_{XY}$とすの組は再帰のは共に森$Y_{v}^{d}=Y$とし，$Y_{v}^{d}\cup\{a\}$$B_{j}=\{\begin{array}{l}(B_{j-1}’\backslash \{a\})\cup\{c\}, (B_{j-1}’\backslash \{a\})\cup\{c\}\cup A が森の場合 (B_{j-1}’\backslash \{b\})\cup\{c\}, otherwise\end{array}$とす$=\{(X_{v}^{d}, Y_{v}^{d}, \{a\})|d\in C\}$に対して，最初に$p’=(B_{i}’)0\leq i<\ell\in \mathcal{P}_{X_{v}^{d}Y_{v}^{d}}$$X_{v}^{d}$$Y_{v}^{d}$$X$への遷移を加えることで道 $p=(B_{i})_{0\leq i\leq\ell}\in$とする．にできる．

$C_{v}=\{a, b\}$ とする．ま
Case 2, $d_{\min}=2$ の場合，ず $C$。

または $C$$\subseteq X$

ならば，一般性を失う$\subseteq Y$。

ことなく $C_{v}\subseteq X$ とする．このとき，$C=\{d\in$$Y|X\cup\{d\}$ は閉路をもたない$e\in C_{v},$ $d\inC$

以上のように多品種流を構成することで，定理 5を得る．

(全域木) とする．各$\}$5

まとめ今後の課題

に対し，$X_{v}^{ed}=(X\backslash \{e\})\cup\{d\},$

辺数が全域木よりも 1 つ少ない森上のマルコフ連鎖に対して，その混交時間が頂点数の多項式で抑えられることを示した．辺数が全域木よりも 1 つ多いとは共に森である．この場合，連結全域部分グラフ上のマルコフ連鎖に対しても同$\{(X_{v}^{ed}, Y_{v}^{ed}, \{e\})|e\in C_{v}, d\in C\}$とする．道 $p’=$様の結果が得られる．
に対して，最初に $X$ から今後の課題としては，任意の辺数の森上のマルコへの遷移を加えることで道フ連鎖や連結全域部分グラフ上のマルコフ連鎖の混$C_{v}\subseteq X$ でも $C$でもない場合，にできる．
$X,$ $b\in Y$ とする． 交時間が頂点数の多項式で抑えられるかどうか解析一般性を失うことなくとする．
より，の組は再帰の仮定を満たす．さらに，$Y_{。}^{ed}=Y$$Y_{v}^{ed}$$\frac{\iota}{2}|X_{v}^{ed}\oplus Y_{v}^{ed}|=P-1$$X_{v}^{ed},$$X_{v}^{ed}\cup\{e\}$$Y_{。}^{ed}\cup\{e\}$

$S$。

$=$

$X_{v}^{ed}$$(B_{i}’)0\leq i<\ell\in \mathcal{P}_{X_{v}^{\epsilon d}Y_{v}^{cd}}$$p=(B_{i})_{0\leq i\leq\ell}\in \mathcal{P}_{XY}$$\subseteq Y$。

$a$

$\in$

$Y_{v}=Y$とすることで， を行う必要がある．

$X_{v}=$$(X \backslash \{a\})\cup\{b\},$$X_{。},$の組は再帰の仮定を満たす．この場合，$Y_{v}$$S$$=$。とする．道$\{(X_{v}, Y_{v}, \emptyset)\}$$p’=(B_{i}’)0\leq i<\ell\in \mathcal{P}_{X_{v}Y_{v}}$にへの遷移を加えることで対して，最初に
道 $p=(B_{i})0\leq i\leq p\in \mathcal{P}_{XY}$ にできる．
$X$から$X_{v}$$C_{v}=\{a, b, c\}$ とする．
Case 3. $d_{m\ln}=3$ の場合，または$d_{\min}=2$ の場合とならば，同様である．そうではない場合，一般性を失うこと$C_{v}\subseteq X$$C_{v}\subseteq Y$

なく $a,$ $b\in X,$$X_{v}^{e}=X,$

らば，$X_{v}^{e},$とする．各 $e\in\{a, b\}$ に対し， [2] J. Fehrenbach, L. R\"uschendorf, Analysis of
Markov chain algorithms on spanning trees,とする． が森な
forests, and connected subgraphs,rootedの組は再帰の仮定を満たす．この場

合，$Y_{v}^{e}$は森 とする．
以降は一般性を失うことなく $e=a$ とする．道 $p’=$$S_{v}=\{(X_{v}^{e}, Y_{。}^{e}, \emptyset)|e\in\{a, b\}, Y_{。}^{e}$$(B_{i}’)_{0\leq i<\ell}\in \mathcal{P}_{X_{Va}Y_{va}}$,$\}$から $p=(B_{i}’)_{0\leq i\leq\ell}\in \mathcal{P}_{XY}$を作るために， において辺 が交換される遷移に$p’$着目し，ある[1] R. Cordovil, M. L. Moreira, Bases-cobases
graphs and polytopes of matroids, Combinatorica, 13 (1993), 157-165.

$c\in Y$$Y_{v}^{e}=(Y\backslash \{c\})\cup\{e\}$$Y_{v}^{e}$

参考文献

$b$

$i\in\{0, \ldots\ell\}$に対して $b\in B_{j}’\oplus B_{j+1}’$とする．このとき，$i\in\{0, \ldots, \ell\}\backslash \{j\}$に対し，$B_{i}=\{\begin{array}{l}B_{i}’, i<ji>j\end{array}$$(B_{i-1}’\backslash \{a\})\cup\{.c\},$Appl. Math., 32 (2005), 341-365.

[3] A. Sinclair, Improved bounds for mixing ratesof Markov chains and multicommodity flow,
Combinatorics, Probability and Computing, 1(1992), 351-370.

[4] 伊里正夫，藤重悟，大山達雄，グラフネッ
トワークマトロイド，産業図書，1986.