修士論文 要旨

Fully dynamic algorithms for graph connectivity and spanning forests
under general vertex updates（グラフ連結性と全域森問題に対する頂点更新に対応した完全動的アルゴリズム）
数理情報学専攻 48-166224
指導教員

1 はじめに中村 健吾
定兼 邦彦 教授

2 動的 DFS

現実世界に現れるグラフ構造は，時間とともに徐々に深さ優先探索 (Depth-First Search, DFS) はよく知変化するものが多い．この構造の変化は，グラフ理論でられたグラフ探索の手法で，線形時間 (O(m + n) 時間)は頂点や辺の追加・削除としてモデル化され，そのようで実行できて，探索の結果として DFS 木 (森) とよばれな変化 (更新) が一つずつ起こるようなグラフを動的グる根付き全域木 (森) が生成される．DFS 木は有向グラ

ラフとよぶ．動的グラフの上では，通常のグラフアルゴ

フの強連結成分分解や無向グラフの頂点間の 2-(辺) 連

リズムは更新のたびに一から走らせる必要があり，効結性判定など，様々なグラフアルゴリズムの道具として率が悪い．そこで，動的グラフの上で効率よく動く動的使われる．本研究で扱うのは，その動的グラフ版であるグラフアルゴリズムを考える．動的グラフアルゴリズ

動的 DFS 問題であり，その目標は，グラフ G への頂点

ムはここ 2,30 年で広く研究され，全点対間最短パスやや辺の追加，削除のたびに G の DFS 木 (森) T を一つ(近似) 最大マッチング，最小カットなど多くの問題 (の出力できるデータ構造を構築することである．

動的版) に対して，アルゴリズムが提案されてきた．

この問題は，2015 年以前に開発されたアルゴリズム

しかし、動的グラフに関する多くの研究は辺更新，すはいずれも，辺追加か辺削除のどちらかしか対応せず，なわち辺の追加や削除しか取り扱っていない．そこで

しかも複数回の更新に渡ったコストの平均 (ならし計算本研究では，頂点の削除および，頂点とその隣接辺を量) は通常の DFS を繰り返し行うより良いものの，1一度に追加するという更新ができる設定を考える．こ更新あたり最悪でかかるコスト (最悪計算量) は通常のれらの更新をここでは (拡張) 頂点更新 (general vertex

DFS と変わらないという問題点があった．一方，2016update) とよぶ*1 ．頂点更新は辺更新を模倣できる上年に Baswana ら [1] が開発した無向グラフ動的 DFSに，グラフの頂点数が変化しうるという辺更新設定にはアルゴリズムは，頂点や辺の追加・削除全てに対応し，ない特徴があり，辺更新より広範な変化を扱える．

かつ 1 更新あたりの最悪計算量が o(m) になり，両方の一方で，辺更新設定でも頂点更新設定をある程度模倣できる．まず前処理の際に，孤立頂点をいくつかグラフ問題を解決した．のちにその時間計算量は Chen ら [2]により少し改善された．に追加しておく．すると，各頂点追加は，追加した孤立

し か し ，こ の 両 者 は い ず れ も 必 要 な 空 間 が頂点のうち 1 つを追加頂点とみなすことで対応でき，1O(m log2 n) ビットであるという欠点を抱えている．こ回の頂点追加や削除は，それに隣接する O(n) 本*2 の辺れはグラフの隣接リスト表現の O(log n) 倍であり，巨の追加や削除で対応できる．しかし，この手法では最初大なグラフには適さない．そこで本研究では，Baswanaに追加した孤立頂点の数しか頂点追加できず，任意個のら [1] のアルゴリズムの空間の圧縮を図ると共に，更新頂点追加に対応することはできない．そこで，本研究で時間計算量の削減に取り組んだ．

は任意個の頂点追加に対応した頂点更新動的グラフアルゴリズムを開発することを目指す．

その結果が表 1 である．本研究で提案したアルゴリ
ズム A,B は，頂点・辺の追加・削除が全てある設定の本研究では，動的グラフ問題の中で，動的 DFS 問下ではいずれも既存のアルゴリズムより更新計算量が題および動的連結性・全域森問題を扱った．これらはい小さく，辺の追加のみの設定でも Chen らの結果 [2] にずれも，動的グラフの中でも特に基本的な問題である．

肉薄している．さらに，必要な空間が O(log n) 倍圧縮されていて，アルゴリズム B ではさらに定数倍圧縮さ*1 頂点更新を考えた設定には他に部分グラフ設定とよばれるものれている．提案アルゴリズムはいずれも，頂点・辺の追もあるが，この設定も (拡張) 頂点更新設定で模倣できる．その意味で呼び名に “general” という単語を入れている．
*2 本稿では n はグラフの頂点数，m は辺数を表すものとする．

加・削除がある下で任意の 2 頂点間の 2-(辺) 連結性という高度な連結性を答えるデータ構造へ応用できる．

Fully dynamic algorithms for graph connectivity and spanning forests under general vertex updates (中村 健吾)

表 1. 各動的 DFS アルゴリズムの必要な空間と

3 動的連結性・全域森

1 更新あたりの最悪時間計算量．

連結性クエリとは，入力された 2 頂点間がグラフで繋がっているかを判定するクエリで，グラフ中のクエリの中でも最も基礎的なものの一つである．グラフの更新とクエリのオンライン列を処理する問題を動的連結性問題，それを解くデータ構造を動的連結性オラクルとよぶ．一方，グラフ更新の下で更新の度にそのグラフの空間 (bit)

更新毎最悪時間計算量(辺追加のみ)(頂点/辺の追加/削除)√O( mn log2.5 n)√O( mn log1.5 n)√O( mn log0.75+ε n)√O( mn log1.25 n)O(m log2 n)O(n log3 n)
2
O(m log n)O(n)√O(m log n)O(n log n)∗(3m + o(m))
O(n log n)
B· log n√∗ m = O(n2 / log n) ならば O(n logε n) まで高速化可能[1][2]
A

表 2. 変換前の辺更新対応連結性・全域森データ構造

全域森に対する変化を出力する問題を動的全域森問題，と変換後の頂点更新対応連結性・全域森アルゴ

それを解くデータ構造を動的全域森データ構造とよぶ．

リズムの更新計算量とクエリ計算量．左列の更大まかに言えば，全域森を維持できれば連結性クエリは新計算量は 1 辺あたり，右列は 1 頂点あたり．

解けるので，動的連結性問題は動的全域森問題に帰着できる．一方で，DFS 森は全域森でもあるので，2 章の動的 DFS アルゴリズムで動的全域森問題は解ける．
動的連結性・全域森問題は動的グラフの中でも最も基礎的な問題で，辺更新設定の下では様々なアルゴリズムが提案されてきた．現在は，辺更新の下では乱択の種類(決定的か Las Vegas か Monte Carlo か) や更新計算量の種類 (ならしか最悪か) によってそれぞれ異なる更新計算量上界が存在するほか，更新計算量とクエリ計算量の下界の関係も研究されている．しかし，頂点更新設定対応する
辺更新データ構造提案した
頂点更新アルゴリズム[5]X√
log2 n1.25
O( m logn + l log)/updatelog nlog2 nO( log)/updatelog nlog nO( log)/querylog nlog nO( log)/querylog n

動的連結性オラクル・ならし計算量・決定的[4]O(log2 n)/updatelog nO( log)/querylog nY√O( m log1.25 n + l log2 n)/updateO(1)/query

動的全域森データ構造・ならし計算量・決定的[3]O(log5 n)/updatelog nO( log)/querylog nZ√O( ml log2.75 n)/updateO(1)/query

動的連結性オラクル・最悪計算量・Monte Carloの下で，しかも任意個の頂点追加ができるようなアルゴリズムはほとんど提案されていない．Baswana ら [1]や本研究の動的 DFS アルゴリズムはその例外である．
そこで本研究では，辺更新のみに対応する動的連結性
オラクルや動的全域森データ構造を，頂点更新かつ任意個の頂点追加に対応するよう変換する効率的な枠組みを提案した．この枠組みを用いて，Wulﬀ-Nilsen [5] やThorup [4] のならし更新計算量データ構造や，Kapron
ら [3] の最悪更新計算量乱択データ構造*3 を実際に変換した．変換前と変換後のアルゴリズムの更新・クエリ計算量を表 2 に示す．
提案したアルゴリズム X,Y,Z の更新計算量はいずれも l に依存している．l はある時点のグラフに対し計算された DFS 森の葉の数である．これは n 以下であり，1 頂点更新は O(n) 回の辺更新に相当するため，アルゴリズム X や Y の計算量は，元のデータ構造をそのまま使うより遅くはない．さらに，比較的密なグラフではl = o(n) になりやすい．具体的には，ランダムグラフ(ER モデル) の下では平均辺数が ω(n log n) であると
*3 このデータ構造は Monte Carlo であり，僅かな誤り確率をもつ．連結性クエリに対し「連結」と答えた場合は必ず連結であるが，「非連結」と答えた場合でも確率 1/poly(n) 以下で連結である．変換後のアルゴリズム Z もこの性質をもつ．

き高確率で l = o(n) となることが知られている．従って，比較的密なグラフに対しては各提案アルゴリズムの更新計算量は小さくなることが期待できる．連結性クエリに関してもアルゴリズム Y,Z では定数クエリ時間を達成した．繰り返しになるが，提案アルゴリズムは元のデータ構造をそのまま頂点更新に使うのと異なり，任意個の頂点追加に対応しているという利点がある．さ
らに，[4, 5] を含め多くの辺更新ならし計算量データ構
造には初期グラフが空でなければならないという制約があるが，提案アルゴリズムにそのような制約は無い．

参考文献[1] S. Baswana, S. R. Chaudhury, K. Choudhary, andS. Khan. Dynamic DFS in undirected graphs: breaking the O(m) barrier. In Proc. SODA, pages 730–739,2016.
[2] L. Chen, R. Duan, R. Wang, and H. Zhang. Improved
algorithms for maintaining DFS tree in undirectedgraphs. arXiv:1607.04913v2, 2016.
[3] B. M. Kapron, V. King, and B. Mountjoy. Dynamicgraph connectivity in polylogarithmic worst case time.
In Proc. SODA, pages 1131–1142, 2013.
[4] M. Thorup. Near-optimal fully-dynamic graph connectivity. In Proc. STOC, pages 343–350, 2000.
[5] C. Wulﬀ-Nilsen. Faster deterministic fully-dynamic
graph connectivity. In Proc. SODA, pages 1757–1769,2013.