修士論文 要旨

円上の交差グラフ族に対するグラフの個数の評価と簡潔データ構造
数理情報学専攻 48196222
指導教員

1 はじめに
簡潔データ構造とは，データを情報理論的下限に近いサイズに圧縮しつつ効率的に様々なクエリに回答できるようなデータ構造のことである．近年，WEB ページやゲノム配列など巨大なデータを扱う機会が増えており，簡潔データ構造の重要性が高まっている．
本論文では，グラフクラスを限定して簡潔データ構造

中島 渓
定兼 邦彦 教授

ラフは単純無向，重みなし，ラベルなしとする．初めに，簡潔データ構造，0 次経験エントロピーを以下のように定義する．
定義 2.1. 簡潔データ構造
基 数 Z の 集 合 の 任 意 の 要 素 に つ い て ，空 間 計 算 量

log Z + o(log Z) ビットで効率的にクエリに答えるデー
タ構造を簡潔データ構造という．

を考える．グラフクラスを限定すると，一般のグラフに

定義 2.2. 0 次経験エントロピー

おいて解くのが困難とされる問題が多項式時間で解けS をアルファベット A 上の長さ n の文字列とする．文たり近似したりすることができる．

字 c ∈ A の S 中の出現回数を nc とすると，S の 0 次経

また，グラフクラスに着目することで，そのグラフの験エントロピー H0 (S) は以下の式のように定義される．

性質を利用した簡潔データ構造を考えることができる．

H0 (S) = Σc∈A

このような研究は，木 [5]，コーダルグラフ [6]，区間グnnc
log .
nnc

ラフ [1] など広く行われてきている．
今回簡潔データ構造を考える対象のグラフクラスは，円上の交差グラフ族である．弦や円上の凸多角形など円上の図形による交差グラフであり，circle グラフや次に，簡潔データ構造において最も基本的なクエリである rank/select を紹介する．

S= s1 , s2 , . . . , sn を ア ル フ ァ ベ ッ ト A =circle-trapezoid グラフ，circle-polygon グラフなどが{0, 1, . . . , σ − 1} 上の文字列とする．ここで，α ∈ Σ含まれる．図 1 は円上の交差グラフ族のグラフの包含に対し，rankα (S, i) を S[1..i] における α の出現回関係を表している．一般化 circle-polygon グラフは本数，selectα (S, i) を S 中で i 番目の α が出現する位論文で導入するクラスであり，circle-polygon グラフと置と定義する．ビットベクトル上及び文字列上での同値なグラフクラスである．

rank/select について，以下の補題が知られている．
補題 2.3 ([3]). 長さ n のビット列 B[1 . . . n] に対し，B 上での rankα , selectα (α = {0, 1}) と access が定数時間で処理できる n + o(n) ビットのデータ構造が存在する．
図 1. 矢印は矢の先のグラフクラスを部分クラスとして含むことを表している．

補題 2.4 ([2]). 任意の α > 0, σ > 1 について，A ={0, 1, . . . , σ − 1} 上の文字列上での rankα , access クエ
リを O(1 + log log σ) 時間，selectα クエリを定数時間

グラフクラスの色は各グラフクラスを表現するのに必要なビット数を表している．グラフクラスの近くの数字は上下界の主要項を記したもので，その中でも赤文字で書いてある数字は本論文で与える上下界である．

2 基本事項計算モデルは n を入力サイズとしたとき， Θ(log n)ビットの word RAM モデルを仮定する．また，扱うグで回答する，nH0 + o(n)(H0 + 1) ビットのデータ構造が存在する．
次に，Range Maximum Query を導入する．全順
序 集 合 上 の 配 列 S = s1 , s2 , . . . , sn に 対 し ，区 間[i, j] (1 ≤ i, j ≤ n)

での Range Maximum Query

は RMaxS (i, j) := arg max sk と表される (最大値が複k∈[i,j]数個出現するときは最も左の位置を返す)．同様にして

円上の交差グラフ族に対するグラフの個数の評価と簡潔データ構造 (中島 渓)

Range Minimum Query も定義される．のビット列 A も追加すると，空間計算量は，補題 2.5 ([4]). S を長さ n の全順序集合上の配列とすn∑

る．2n + o(n) ビットで，S は保持せずに，定数時間j=1

で RMaxS , RMinS クエリに回答するデータ構造が存在する．

≤k∑(dj − 1) log
ni · i log

i=2N −n+ O(N )dj − 1n− n log n + O(N log k)i

補題 3.2. 以上の表現は k = o(log n/ log log n) のと

3 円上の交差グラフ族の個数の上下界

き，定理 3.1 の下界と漸近的に一致する．

円上の交差グラフとは，弦や円上の凸多角形などの円上の図形による交差グラフのことをいう．

4 簡潔データ構造

一 般 化 circle-polygon を ，円 上 に 頂 点 を も ち ，任意の頂点数で，辺は弦または弧である図形と定義する．一般化 circle-polygon による交差グラフを一般化

circle-polygon グラフと呼ぶこととする．一般化 circlepolygon グラフは circle-polygon グラフと同値なグラフクラスである．

2 頂点が隣接するか判定する adjacent，隣接する頂点集合を求める neighborhood，隣接する頂点数を求める

degree クエリを考える．
上記の S ′ , F, A に加えて，補題 2.5 を用いて，注目する頂点に関して出ていく辺の終点/入ってくる辺の始点を管理するデータ構造を追加で持つ．F, S ′ はそれぞれこのグラフクラスに対し，個数の上下界を与える．

補題 2.3, 2.4 のデータ構造で持つとすると，空間計算量定理 3.1. k (k = polylog(n)) 個以下の頂点をもつ

UB + o(UB) ビット (UB は上述の上界) で，adjacent,n 個の一般化 circle-polygon により構成されるグラフ

neighborhood, degree にそれぞれ O(k)，O(|degree(u)|·クラスを考える．このとき，頂点数 i (2 ≤ i ≤ k)k log log n)，O(|degree(u)| · k log log n) 時間で回答すの一般化 circle-polygon の個数を ni 個とする．N =ることができる．

∑ki=2 i · ni , n = (n1 , n2 , · · · , nk ) とおく．Pn,k,n をこのようなグラフの総数とすると，以下の式が成り立つ．
k∑nlog Pn,k,n ≥ni · i log − n log n − O(N log log n)ii=25 おわりに
circle-polygon グラフと同値なグラフクラス，一般化
circle-polygon グラフを導入し，個数の上下界と簡潔データ構造を与えた．このグラフクラスは，circle グラ

次に，上界を与える．コーナー文字列 S を定義する．

フや circle-trapezoid グラフなどを含むグラフクラスで空文字列の状態から，円上の任意の点から始まり時計あるから，円上の交差グラフ族に対して，統一的なアプ回りに円を一周する．このとき，一般化 circle-polygon

ローチを提示したといえる．の頂点が現れるたびに，S にその頂点が属する一般化

circle-polygon の番号を S の末尾に追加した文字列がコーナー文字列である．また，一般化 circle-polygon の番号はこの一周の間に一般化 circle-polygon が現れた順番とする．
コーナー文字列 S を圧縮する．S の長さは N =∑ki=2 ni · i で文字 i (2 ≤ i ≤ k) は ni 回出現することに注意する．各文字 i について S 中での最初の出現は長さ N のビットベクトル F で表現できる．他の文字′については，長さ N − n の文字列 S に格納する．S′中には，文字 i は di − 1 回出現する．ここで，di は一般化 circle-polygon i の頂点数とする．S ′ を 0 次経験エントロピーに圧縮し，各辺が弧か弦かを表す長さ N

参考文献[1] H. Acan, S. Chakraborty, S. Jo and S. R. Satti: Succinct data structures for families of interval graphs.
In WADS, vol. 11646 of LNCS, Springer, 2019, pp.
1–13.
[2] J. Barbay, F. Claude, T. Gagie, G. Navarro and Y.
Nekrich: Eﬃcient Fully-Compressed Sequence Representations. Algorithmica, 69(1), 2014, pp. 232–268.
[3] D. R. Clark and J. I Munro: Eﬃcient suﬃx trees on
secondary storage. SODA 96, 1996, pp. 383–391.
[4] J. Fischer and V. Heun: Space-eﬃcient preprocessing
schemes for range minimum queries on static arrays.
SIAM Journal on Computing 40(2), 2011, pp. 465–492.
[5] J. I. Munro and V. Raman: Succinct representationof balanced parentheses and static trees. SIAM J.
Comput., 31(3), 2001, pp. 762–776.
[6] J. I. Munro and K. Wu: Succinct data structures forchordal graphs. In ISAAC, 67, 2018, pp. 1–12.