数理解析研究所講究録
第 1562 巻 2007 年 92-9892

組合せ構造の列挙とサンプリング
東海大学理学部情報数理学科 松井泰子 (Yasuko Matsui)

Department of Mathematical Sciences
Tokai University

1

列挙とサンプリング与えられた集合 の要素で, 性質 $P$ を満たすものを全て求めることを列挙 (enumeration)
とい列挙を行う問題を列挙問題 (enumeration problem) という. 列挙問題においては,解を 1 っ見っけることは一般に容易である (解を 1 つ求めるのも困難である列挙問題も存在する). しかし, 解を全て見つけたという保障をすることは容易では無い. また, 単純にメモリに解を蓄え, 解が 1 つ見つかる度に付き合わせて重複しているか否かをチェック等すると, 解集合の大きさは指数個にのぼり, すぐにメモリ限界に達する. そのため,高速に解を列挙しかつメモリを効率良く使用するアルゴリズムの開発が望まれるようになった. 列挙問題を解くアルゴリズムは列挙アルゴリズムと呼ばれ, 1960 年代頃から研究されている. 当初は理論的な興味から列挙アルゴリズムが提案されたが, 近年, コンピュータの処理能力の飛躍的な進歩とメモリの低廉化により, 列挙アルゴリズムの実装が可能となり, 列挙問題に対する列挙アルゴリズムの構築が注目を集めている.
列挙アルゴリズムの計算時間の算定は, 通常, 問題の入力サイズと解の出力数 $N$ の関数によるオーダーで表される. 計算時間が問題の入力サイズと $N$ の多項式のオーダーでおさえられる時, 列挙アルゴリズムは出力多項式時間 (output polynomial) であると呼ばれる. 特に, 解を 1 つ出力してから次の解の出力に要する時間が, 問題の入力サイズの多項式のオーダーでおさえられる時, アルゴリズムは多項式時間遅延 (polynomial delay) であるという [18]. 列挙アルゴリズムの効率化に関しては, 計算時間の短縮以外に, 出力の大きさを縮小するコンパクト出力 (compact output) の研究も行われている. 解を陽に出力するのでは無く, 直前の解との差分のみを出力するなどの効率化を図るのである.
列挙アルゴリズムで用いられる代表的は枠組みは, バックトラック法, 分割探索法, 逆探索法 (reverse search)[2] 等が挙げられる. ここでは本稿で扱う, 逆探索法について触れる. 逆探索法は, 各頂点が列挙される解に対応する木 (列挙木) を陰に構築し, 列挙木の上を探索して解を列挙する方法である. 列挙木は, 頂点間の親子関係によって定義される. すなわち, 列挙木の根に対応する頂点以外では, 自分の親となる頂点が一意に定義できるというものである. 一般にそのような親子関係は容易には定義できない. 列挙木の構
築は, 親が子の候補 (子であるものを全て含む) が全て探索でき, 子からは自分の親が同定できれば実現できる. 逆探索法では, 列挙木の根に対応する頂点から順に子の候補を探索し, 子の候補が見つかる度に, 子から親を同定して親子関係をチェックし, 親ならば子 (解) を出力するという操作を, 子の候補が探索される限り再帰的に繰り返す. この繰り返しにより, 列挙木を陽に構築することなく全ての頂点が探索できるのである. 逆探索法に関しては, [12] に提案者による日本語の解説がある. 列挙アルゴリズムの詳細に関しては, 文献 [20] を参照されたい.
$\mathcal{F}$$Aa$$N\mathcal{P}$93

列挙アルゴリズムが提案される一方, 性質 $P$ を満たすものをランダムにサンプリングしたいという要求がある. 列挙されるものの個数は指数個に膨れ上がるため, そのうちの一部を求めて利用するというものである. 例えば, 統計で分割表のデータを検定する時に,周辺和を固定した分割表をサンプリングして推定量を計算する. 分割表のデータを正確に検定する場合は, 周辺和を固定した分割表を全て列挙する必要があるが, その総数が膨大となるため, 列挙の代わりに一様ランダムにサンプリングした分割表を用いて検定を行う. そのため, 周辺和を固定した分割表のサンプリングを, マルコフ連鎖モンテカルロ法(MCMC 法) 等によって実現するのである. 近年は計算量の観点から, マルコフ連鎖の撹拝時間 (mixing time) が問題の入力サイズ, 誤差, 分割表の総数による多項式のオーダーでおさえられる, 実用的なマルコフ連鎖の構築等の研究が盛んである $[1],[3],[4],[5],$ $[7],[9],[10]$ ,$[14],[15],[17],$ $[19],[23],[27]$ .

2

コーダルグラフの perfect sequence の列挙

本稿では, 以降においてコーダルグラフ上で定義できる perfect sequence に対する列挙アルゴリズムを提案する. コーダルグラフは幅広い応用が知られるグラフである. 例えば, 統計ではコーダルグラフは分解可能モデルや, ベイジアンネットワークにおける周辺確率の局所計算等にも活用されている. 数理工学においては, 半正定値計画問題, 信号処理, 数値計算, 準=n ートン法等でコーダルグラフが重要な役割を果たしている. また,一般のグラフ上では解決が困難な問題が, コーダルグラフ上では比較的容易に解ける場合もある. このような背景から, コーダルグラフに関する研究が, 多様な分野の研究者の注目を集めている. ここでは, コーダルグラフに付随した perfect sequence という順列について考える. 与えられたコーダルグラフの perfect sequence の列挙によって, 統計や可換代数の諸問題が解決できる [14] [16]. そのため perfect sequence の列挙に対する要求が高
いが, 列挙される個数が指数オーダーとなり, 列挙されたものをメモリに蓄える単純な方法では列挙は容易でない. 既存の研究で e2 perfect sequence をランダム生成するアルゴリズムは存在するが, 列挙アルゴリズムは (筆者の知識の限りでは) 未だ提案されていない.
以上のような背景から, 本稿では perfect sequence を列挙するアルゴリズムを提案する.
まず諸定義を行う. $V$ を頂点集合, $E$ を辺集合とするグラフ $G=(V, E)$ において, $G$ 中の長さ 4 以上の閉路が必ず弦をもつときコーダルグラフとよぶ. $C,$ $S$ を各々 $G$ 中の極大ク
リーク (maximal clique) の集合と極小頂点分離 (minimal vertex separator) 集合とする. 木$T=(C, \mathcal{E})$ が $G=(V, E)$ のクリーク木であるとは, 任意の二っの極大クリーク$C_{2}\in C$$T$
上で$c_{a}\inC$と,がに対し,を結ぶ一意なパス中にある極大クリーク$G$$G$成り立っことである.
がコーダルグラフである必要十分条件は,にクリーク木が存在することである [13]. 一般に, コーダルグラフにはクリーク木が複数存在する. Kumar andMadhavan は, クリーク木の総数を数え上げるアルゴリズムを提案している [21]. クリーク
$C_{1}\cap C_{2}=S$$C_{2}\in C$ について,木 $T=(C,\mathcal{E})$ 上で隣接する任意の二っの極大クリークとなる極小頂点分離集合 $S\in S$ が存在する. $G$ 中の極大クリークを, $K$ と$i=1,$し, 添え字集合を $\mathcal{I}=\{1, \ldots, K\}$ とする. 置換 :$k=1,$について,, $K$と$k=2,$, $K$ を各々 $H_{\pi(k)}=C_{\pi(1)}\cup\cdots\cup C_{\pi(k)},$ $S_{\pi(k)}=H_{\pi(k-1)}\cap C_{\pi(k)}$ と定義す
$C_{1},$$C_{1}\cap C_{2}\subseteq c_{s}$$C_{1},$ $C_{2}$$C_{1},$$C_{k},$$\pi$$S_{\pi\langle k)},$$\ldots$$\mathcal{I}arrow \mathcal{I}$$H_{\pi\langle k)},$$\ldots$$\ldots$

94が極大クリークの perfect sequence であるとは, 各がクリークであり, すべてのについてとなる $k’<k$ が存在することである. 極大クリークの perfect sequence が存在する必要十分条件は, $G$ がコーダルグラ
フであり, すべての について $S_{\pi(k)}\in S$ で,, .. . , $S_{\pi(K)}\}\in S$ を満たすことである.
ただし,には同じ極小頂点分離集合 $S$ が複数現れるかもしれない.
2006 年, 原と竹村は, 与えられたコーダルグラフから perfect sequence をランダム生成するためのマルコフ連鎖の構築法を提案した [14]. 彼らが提案したマルコフ連鎖は連結な2 部グラフ $B=(V_{1}, V_{2}, E)$ である. 頂点集合
は各々, クリーク木の集合と perfectsequence の集合に対応している. クリーク木 $u\in V_{1}$ と perfect sequence $v\in V_{2}$ が相互に構築可能である場合, 有向辺 $(u,v),$ $(v, u)\in V_{1}xV_{2}$ が存在するグラフである. 一般に 1 つのクリーク木から構成できる perfect sequence は複数存在する. また 1 っの perfect sequenceから構成できるクリーク木も複数存在し, 2 部グラフ $B$ は連結である. 彼らのアイデアは,から前出のように構築したマルコフ連鎖上を,へ,から斑へと交互にランダムに遷移して perfect sequence をサンプリングすることである. 遷移は, Laurizen によって提案された 2 っのアルゴリズム [22], すなわち, (1) 任意のクリーク木から perfect sequenceをランダム生成するアルゴリズム, (2) 任意の perfect sequence からクリーク木をランダム生成するアルゴリズム, を適用している.
以降では, 与えられたコーダルグラフから perfect sequence を列挙する, 以下のような列挙問題を考える.
る. 列

$\pi$

:

$C_{\pi(1)},$ $C_{\pi(2)},$$\ldots,$$C_{\pi(K)}$$S_{\pi(k)}$$k\geq 2$$S_{\pi(k)}\subset C_{\pi(k’)}$$k$$S_{\pi(2)},$$\ldots,$$\{S_{\pi(2)}$$S_{\pi(K)}$$V_{1},$$V_{1}$$V_{2}$$V_{2}$$\pi$$V_{2}$$\pi$

Problem AllPerfectSequences
INPUT: コーダルグラフ $G=(V, E)$
OUTPUT: $G$ の perfect sequence を重複無く全て.
$\pi$上の列挙問題に対し, 次のような列挙を考えるのが自然であろう. まず, コーダルグラ
フ $G$ のクリーク木を列挙し, クリーク木が得られるたびにその perfect sequence を列挙するのである. しかし, この方法では perfect sequence の重複は避けられない. 従って,列挙アルゴリズムの枠組みの適用が望まれる. 提案する列挙アルゴリズムでは, perfectsequence の重複を避けるために 「逆探索法」 の枠組みを用いて実現する.

2.1
まず,

コーダルグラフのクリーク木の列挙
コーダルグラフからクリーク木を列挙する列挙問題を考える.

Problem All-CliqueTreesINPUT: コーダルグラフ $G=(V, E)$
OUTPUT: $G$ のクリーク木 $T=(C,\mathcal{E})$ を重複無く全て.
コーダルグラフから生成される, クリークグラフと呼ばれる重み付きグラフの概念を導入すると, 列挙問題 All-CliqueTrees は, 以下に挙げるクリークグラフ中の最大全張木の列挙問題 All-MaximumSpam ngTrees に帰着できる. コーダルグラフ $G=(V, E)$ のクリー
$i$

95

中の各頂点 $v\in C$ は $G$ 中の極大クリークに一対一対応し,$G$ 中の極大クリークについてが成り立っとき,に対応する$v_{2}\in C$ 間を辺の頂点の重みは,で結んだグラフである. 辺, すなわちの極小分離集合の頂点数で与える. 最適化の分野では, コーダ
ルグラフ $G$ のクリークグラフの最大全張木は, コーダルグラフ $G$ のクリーク木 $T$ に一対一対応することが知られている. よって, 列挙問題 AlLCliqueTrees は, 以下のコーダ
ルグラフ $G$ のクリークグラフ
中の最大全張木の列挙問題 All-MaximumSpam $ingTrees$
クグラフ$G_{c}=(C, \mathcal{E}_{c})$とは,$G_{c}$$C_{1},$ $C_{2}\subseteq C$$G_{c}$$C_{1},$ $C_{2}$$\{v_{1}, v_{2}\}\in \mathcal{E}_{c}$$v_{1},$$|C_{1}\cap C_{2}|$$C_{1}\cap C_{2}\neq\emptyset$$\{v_{1}, v_{2}\}\in \mathcal{E}_{c}$$C_{1},$ $C_{2}$$G_{c}$$G_{c}$と等価である [21].
Problem All 1aximumSPanningTreesINPUT: コーダルグラフ $G=(V, E)$ のクリークグラフの最大全張木を重複無く全て.
OUTPUT:$G_{c}=(C,\mathcal{E}_{c})$$G_{c}$

列挙問題 All-MaximumSpanningTrees は, 重み付きグラフ中の最大全張木の列挙アルゴリズム ([11] 等) を適用することで実現出来る. 最大全張木の列挙に要する総計算時間はである. ただし, $N$ は列挙する最大全張木の総数である.

$O(|C|+|\mathcal{E}_{c}|+N\sqrt{|\mathcal{E}_{c}}|)$

2.2

クリーク木の perfect sequence の列挙

ここでは, 列挙問題 $Al1_{-}MaximumSpanningTrees$ で得られる最大全張木に対応するクリーク木から, perfect sequence$\pi$を列挙するために, 以下の列挙問題を考える.

Problem All 工憶 $erfectSequences_{-}from_{-}CliqueTree$INPUT: コーダルグラフ $G=(V, E)$ のクリーク木 $T=(C, \mathcal{E})$OUTPUT: $T$ の perfect sequence を重複無く全て.
$\pi$

クリーク木 $T$ の perfect seqeunce は, 以下の操作で構成できる. $T$ 中の任意の頂点を根とし, 根から葉に向けて辺に向き付けをした根付き木 $T’$ を作ると, $T’$ 上でトポロ$\pi$ジカル順序 が定義できる. このトポロジカル順序 は perfect sequenceの定義を満たす. よって, 列挙問題 $AllPerfectSequencesfrom$-CliqueTree は以下の列挙問題$\sigma$$\pi$$\sigma$

All-TopologicalOrdering と等価である.
Problem $Al1_{-}TopologicalOrderi$ng
INPUT: コーダルグラフ $G=(V, E)$ のクリーク木 $T=(C, \mathcal{E})$$OU\Gamma PU:T$ から構成できる根付き木上のトポロジカル順序を重複無く全て.
列挙問題 $Al1_{-}Topologica10rdering$ は, 非巡回的グラフのトポロジカル順序を列挙す
る列挙アルゴリズム ([2],[26]) で実現できる. トポロジカル順序の列挙に要する総計算時間は $O(|C|+N’|C|^{2})$ である. ただし, $N’$ は列挙するトポロジカル順序の総数である. 前
出の 2 つの列挙問題 All-MaximumSpamingTrees, All-MaximumSpamingTrees を解くことで, perfect sequence を全て求めること可能となるが, 明らかには重複して出力さ$\pi$れるため, それを避ける枠組みの提案が必要となる. 本稿では, 逆探索法で用いられる96解の間の 「親子関係」 を利用することで, 重複を避けた列挙を実現する. クリーク木を親, perfect seqeunce を子とする親子関係である. 一般に 1 つの perfect sequence から複数のクリーク木が生成できるが, それらの中から一意な親を同定する. 具体的には次の操作を行う. クリーク木 $T$ において, $T$ 中の頂点を 1 っ根と定めて根付き木 $T’$ を作り,$T’$ 上のトポロジカル順序を列挙する. トポロジカル順序が得られる度に, 以下に$T^{\star}=T$説明するようにして から一意なクリーク木野を作成する.
ならば,を $T$ のperfect sequence として出力する. まず, クリークグラフの頂点をトポロジカル順序$\sigma(C_{\pi(1)}, C_{\pi(2)}, \ldots, C_{\pi(K)})$ に従って並べ,各クリークグラフの辺に向き付けをして有向辺 $(C_{\pi\langle:)}, C_{\pi(j)})(i<j)$ とし, 辺の重みは 4 と同じである重み付き有向グラフを作成する. 次に, $G’$ の根以外の各頂点において, 頂点に入る有向辺から辺上の重みが最大であるものを選ぶ. そのような辺が複数存在する場合は, そのうち添え字の 1 番小さいものを選ぶことにする. 以上のようにして辺を選ぶと, クリークグラフから木 $T’$ が一意に得られ, 木 $T’$ の辺を無向にしたグラフ鮮はクリーク木である.
最後に, 提案した列挙アルゴリズムの計算量と記憶容量を示す.
$\sigma$$\sigma$$\sigma$$\sigma$$G_{c}$$\{C_{\pi(i)}, C_{\pi(j)}\}$$G^{j}$

定理 [松井 [25]] 与えられたコーダルグラフ $G$ の perfect seqeuce の列挙は, $G$ のクリーク
木 $T$ と perfect sequence の間に親子関係を導入することで実現できる. 列挙に要する計算時間はである. ただし,は $G$ のクリークグ, 記憶容量は$G$
はラフの頂点数,のクリークグラフの辺数, $N$ は列挙されるクリーク木の総数,は列挙される perfecrt sequence の総数である.
$O(NN^{\star}(|C|^{2}+|\mathcal{E}_{c}|))$$O(|C||\mathcal{E}_{c}|)$$C$$N^{\star}$$|\mathcal{E}_{c}|$$\blacksquare$

参考文献[1] D. ALDOUS, Random walks on finite groups and rapidly mixing Markov chains, in A.
Dold and B. Eckmann, eds., S\’eminaire de Probabilit\’es XVII 1981/1982, vol. 986 ofSpringer-Verlag Lecture Notes in Mathematics, Springer-Verlag, New York, (1983),

pp. 243-297.
[2] D. AVIS AND K. FUKUDA, Reverse search for enumeration, Discrete Appl. Math.,
65(1996), pp.21-46.
[3] R. BUBLEY AND M. DYER, Path coupling: A technique for proving rapid mixing inMarkov chains, $S8th$ Annual Symposium on Foundations of Computer Science, IEEE,San Alimitos, (1997), pp. 223-231.
[4] R. BUBLEY Randomized Algorithms : Approxzmation, Generation, and Counting,Springer-Verlag, New York, 2001.
[5] F. R. K. CHUNG, R. L. GRAHAM, AND S. T. YAU, On sampling with Markovchains, Random Structures and Algo rithms, 9 (1996), pp. 55-77.

97[6] P. DIACONIS AND A. GANGOLLI, Rectangular arrays with fixed margins, in D.
ALDOUS, P. P. VARAIYA, J. SPENCER, AND J. M. STEELE (Eds.), IMA VOlumes
on Mathematics and its Applications, 72 (1995), pp. 15-41, Springer, New York.

[7] P. DIACONIS AND L. SALOFF-COSTE, Random walk on contingency tables with
fixed row and column sums, Technical Report, Department of Mathematics, (1995),Harvard University.
[8] P. DIACONIS AND B. STRUMFELS, Algebraic algorithms for sampling from conditional distributions, The Annals of Statistics, 26 (1998), pp. 363-397.
[9] M. DYER AND C. GREENHILL, Polynomial-time counting and sampling of two-rowed
contingency tables, Theoretical Computer Sciences, 246 (2000), pp. 265-278.

[10] M. DYER, R. KANNAN, AND J. MOUNT, Sampling contingency tables, RandomStructures and Algorzthms, 10 (1997), pp. 487-506.

[11] G. N. FREDERICKSON, Data structures for on-line updating of minimum spannning
trees, SIAM J. Comput., $14(1985),pp.781-798$ .
[12] 福田公明, 逆探索とその応用, 離散構造をアルゴリズム
47-78.

, 近代科学社 (1993), $pp$ .

[13] F. GAVRIL, The interersection graphs of subtrees in trees are exactly the chordalgraphs, J. Combin. Theory Ser. , 116 (1974), pp. 47-56.
$B$[14] H. HARA AND A. TAKEMURA, Boundary cliques, clique trees and perfrt sequencesof maximal cliques of a chordal graph, Technical Report, METR, 2006-41, Department of Mathematical Infomatics, University of Tokyo, 2006.

[15] D. HERNEK, Random generation of 2 $xn$ contingency tables, Random Structuresand Algorithms, 13 (1998), pp. 71-79.
[16] J. HERZOG, T. HIBI, X. ZHENG, Monomial ideals whose powers have a linearresolution, Math. Scand., 95 (2004), pp. 23-32.
[17] M. R. JERRUM AND A. SINCLAIR, The Markov chain Monte Carlo method: anaPproach to aPproximate counting and integration, in $Appm\dot{\alpha}mation$ Algorithm for
NP-hard problems, D. S. HOCHBAUM (Ed.), PWS publishing, Boston, 1997, pp.

482-520.
[18] D. S. JOHNSON, M. YANNAKAKIS, AND C. H. PAPADIMITRIOU, On generating all
maximal independent sets, Information Processing Letters, 27(1988), pp. 119-123.
[19] R. KANNAN, P. TETALI AND S. VEMPALA, Simple Markov chain algorithm forgenerating bipartite graphs and tournaments, in 8th Annual Symposium on DiscreteAlgorithms, ACM-SIAM, San Francisco, California, 1997, pp. 193-200.

98[20] 久保幹雄, 田村明久, 松井知己編, 「応用数理計画ハンドブツク」 , 朝倉書店 (2002).

[21] P. S. KUMAR AND C. E. V. MADHAVAN, Clique tree generation and new subclassesof chordal graphs, Discrete Appl. Math. 117(2002), pp. 109-131.
[22] S. L. LAURIZEN, Graphical models, Clarendon Press, Oxford (1996).

[23] T. MATSUI, Y. MATSUI AND Y. ONO, Random generation of 2 $x2x\cdots\cross J$
contingency tables, Theor. Comput. Sci., $326(1- 3)(2004)$ , pp. 117-135.
[24] Y. MATSUI AND T. UNO, On the enumeration of bipartite minimum edge colorings, Graph Theory in Paris, Prvceedings of a Conference in Memory of Claude
Berge, $\pi ends$ in Mathematics, Birkhaeuser Boston Inc., (2006), pp. 271-285.
[25] Y. MATSUI, An algorithm for generating all perfect seqeunces of a chordal graph,preprint.
[26] G. PRUESSE AND F. RUSKEY, Generating linear extension fast, SIAM Joumal ofComputing, 23,2(1994), pp. 373-386.
[27] A. TAKEMURA AND S. AOKI, Some characterizations of minimal Markov basis forsampling from discrete conditional distributions, TechnicaZ Report METR 2002-04Dept. of Mathematical Engineering and Information Physics, Faculty of Engineering,
The University of Tokyo, 2002.