Minimum Arborescence Algorithm

個人的メモ

今まで使っていない(根ではない)頂点から始めてその頂点に入ってくる辺のうち $１$ 番コストの小さいものにたどるという操作を繰り返す. その最中にサイクルが生じる場合があるが, その場合はそのサイクルを $1$ つの頂点に圧縮して, またその頂点に入ってくる辺のうち $１$ 番コストの小さいものをたどるというような操作を繰り返す. このとき, "コストの $1$ 番小さい辺" というのは少し語弊があり, 正確には "サイクルを開くためにかかるコストが $1$ 番小さい辺" を選んでくることにする.
このアルゴリズムについてのより詳しい説明は このブログの記事 がわかりやすいと思います.
正当性の証明は複雑だが, 記事のように圧縮するサイクル $C$ の辺のうち, $|C| - 1$ 本の辺を使う最小全域有向木が存在することを用いた証明や全域有向木多面体上の LP を考え, その相補性条件を元に最適性を示す証明などがある.
以下の実装は基本的な考え方は同じだが計算量の意味でより高速な $\O (n \log n + m)$ time の実装となっている.
先に言うとアルゴリズムが難解というより, 実装において気をつけないといけないことが色々あり, $\O (n \log n + m)$ 時間を達成するのはかなり大変. 個人的に体感で $\O (m \log n)$ アルゴリズムの $5 \sim 6$ 倍くらい大変だと思うのと, 特に競プロにおいては $\O (m \log n)$ と $\O(n \log n + m)$ の違いが効いてくることはほとんどないのと, なので物好きな人だけ実装することをおすすめする. 前提として $\O (m \log n)$ の Chu-Liu / Edmond のアルゴリズムと FibonacciHeap を完全に理解していることが必要になる. 特に Dijkstra や Prim の高速化と異なり, FibonacciHeap をただ blackbox 的に適用するだけではうまくいかない.

以下に雑な備忘録を書くが, 個人的にはまず自分で $\O (n \log n + m)$ time を実現するアルゴリズムをちゃんと考えてみる方が最終的に理解は早いと思う. 表記を分けるのがめんどくさくて以下で元々の頂点かその頂点の縮約された後の頂点かが ambiguous になっているが実装する際には結構気を使う必要がある.
(基本の流れ)
各頂点ごとに Fibonacci Heap を持ち, その頂点に入ってくる辺の出発頂点を管理する. そして各頂点は常に高々 $1$ つのヒープに含まれる. 例えば今まだたどっていない頂点 $v$ を見ているとする. このとき頂点 $v$ に入ってくる辺 $(u, v)$ をすべて見て, その出発点である頂点 $u$ を頂点 $v$ の持つヒープに入れる.
「このとき頂点 $u$ がすでに他の頂点のヒープに含まれているときそのヒープから頂点 $v$ のヒープに move するという操作をする. 重要なこととして今考えている問題設定においてこの move はならし $\O (1)$ の計算量でできるということがある(そのヒープから delete して, 頂点 $v$ のヒープに push するみたいなことをすると delete 回数が最悪 $m$ 回ぐらいになリ計算量的にダメ). move については後に述べる. 」
このときの頂点 $u$ のキー値は $(u, v)$ のコスト + ($v$ に入ってくる辺を変えたときにかかるコスト) とする(このあたりは Chu-Liu / Edmond と同じである). そして delete_min をすることで頂点 $v$ に入ってくる辺の中でサイクルを開くためにかかるコストが $1$ 番小さい要素(例えば $u^{\ast}$ とする)を見つけて, 次に頂点 $u^{\ast}$ を見るみたいなことを繰り返す.
例えば今すでにたどったが, まだ確定していない頂点 $v$ に再びたどり着いたとすると, サイクルができるので圧縮する. サイクルに含まれる頂点集合を $S$ としたとき $S$ 内の頂点に終点を持つ辺で同じ出発点 $u$ を持つものが複数存在しうるが, 今後の操作においてこのうちのちょうど $1$ つの辺のみを保持すれば十分である($v_i \in S$, $(u, v_i)$ のコスト + ($v_i$ に入ってくる辺を変えたときにかかるコスト) が最小のものだけ考える). つまりサイクルを $1$ 点に縮約した後の頂点を $v^{\ast}$ とすると, サイクル内のヒープをマージしてできた頂点 $v^{\ast}$ のヒープには $S$ に入ってくる辺の出発頂点 $u$ がすべて入っていて, そのキー値は "$v \in S$ で 辺 $(u, v)$ のコスト + ($v$ に入ってくる辺を変えたときにかかるコスト)" の最小値とする. そしてできた頂点 $v^{\ast}$ のヒープから delete_min でまたキー値の $1$ 番小さい要素を見つけて... を繰り返す.

(ポイント 1)
頂点 $v$ に入ってくる辺を変えたときにかかるコストを頂点 $v$ の change cost と言うことにする. 新たに頂点 $v^{\ast}$ のヒープから最小キー値の要素を削除したときを考える. その要素が出発頂点 $u$, 辺 $(u, v)$ の要素であったとする. このとき $v^{\ast}$ に縮約されている頂点の change cost に "- 辺 $(u, v)$ のコスト - (頂点 $v$ の change cost)" を加算する. これは頂点を遅延加算つきの Union Find で管理することで効率良くできる. そして各頂点 $v$ の change cost を知りたいときは通常の Union Find の Find 操作と同様にしてコストを知ることができ, また計算量も変わらない. ここで change cost の変更によって頂点 $v^{\ast}$ のヒープ内の要素のキー値が変わるが, 各キー値が一様に増える or 減るなのでヒープの構造自体に変化はないことに注意する. また $y$($\ge x a(k, x)$ ($k$ は定数, $a(k, x)$ はアッカーマン関数の逆関数)) 回の Find 操作, $x - 1$ 回の Union 操作からなる任意の操作列についてかかる総計算量は $\O (y)$ であることも知られていて, そして最終的にこのアルゴリズムにおいて $y$ は $\O (n \log n + m)$ となるので Union Find を用いて頂点をマージしたり, change cost を求めたりというのは $\O(n \log n + m)$ の計算量ででき, Union Find 部分にかかる計算量は問題ない. ただこれは根を大きい方に付ける + 経路圧縮を行った場合の Union Find の話なのでよくある $\O(m \log n)$ time の実装のように根を自由に取ることはできない(⇒ ポイント 4).
(ポイント 2)
Fibonacci Heap の move 操作は例えば要素 $e$ をヒープ $h1$ からヒープ $h2$ に移動させるとき $e$ を根とする部分木を $h1$ から削除し, $h2$ のヒープの根にすることを指す. このとき $h1$ について要素 $e$ の親が存在するなら子が $1$ つ減ったことになるのでもし mark されていたら その親を $h1$ のヒープの根にするみたいなことを decrease_key と同様に再帰的に繰り返す. この操作は当然ならし $\O (1)$ で可能であるが, このとき $e$ だけでなく $e$ を根とする部分木内の頂点がすべて $h2$ に行くことになり, 本来のヒープとは異なるヒープに含まれるみたいなことが起きる. また要素 $e$ のキー値は move によって変化するので, 要素 $e$ の子で $e$ よりキー値の小さいものが存在しうることになり, ヒープの条件は厳密には壊れる.
各要素についてその要素が含まれるべき正しいヒープを home heap と呼ぶことにする. このとき各ヒープについてそのヒープを home heap とする要素については先祖の方が小さいという条件が成り立つ & ヒープの根となっている要素はすべてそのヒープを home heap とする & delete_min を行う際にそのヒープを home_heap とする要素は常にそのヒープに含まれる という条件を満たすように管理できるのでヒープの条件が壊れていても結果には影響しないことが分かる. 特に $3$ つ目の条件は本アルゴリズムだから成り立っているのであって一般の状況で move をならし $\O (1)$ で行うのは厳しそう(ただ $3$ つ目の条件をうまく満たせるようにできる状況はよくありそうなので他のアルゴリズムにも応用はできそう). また上記の操作では minimum(最小キー値の要素) をうまく管理できないので top()(最小キー値の参照) には "そのヒープを home_heap とする要素は常にそのヒープに含まれる" という条件が成り立つもとであってもならし $\O (\log n)$ かかる(今回は top() が常に delete_min と結びついているので特に問題はない).
よって move 操作のおかげで結局のところならし $\O (\log n)$ かかる delete_min の回数は $\O (n)$ 回で済み, 他の操作を行う回数は $\O(n \log n + m)$ 回となるなので, 結局 Fibonacci Heap に関連する計算量は $\O(n \log n + m)$ time であることが言える.
(ポイント 3)
まだ気をつけるべき点はあってそれは辺を見る回数をちゃんと $\O (m)$ にすることである. これは先に述べた "今後の操作においてこのうちのちょうど $1$ つの辺のみを保持すれば十分である($v_i \in S$, $(u, v_i)$のコスト + ($v_i$ に入ってくる辺を変えたときにかかるコスト) が最小のものだけ考える)" の部分に効いてくる. 結論から言えばこれは passive_list というリストで辺を管理することで可能になる. 具体的には, すでに見た辺であるが, その出発頂点が対応する Fibonacci Heap に含まれていないような辺 $(u, v)$ (要をするに出発頂点が他のヒープに move された辺) を passive_list[$v$] に保持しておく. 先に述べたようにまだたどっていない頂点 $v^{\ast}$ に注目しているときに入ってくる辺 $(u, v)$ をすべて見て, もし頂点 $u$ がすでに別の頂点のヒープに含まれているならそれを頂点 $v^{\ast}$ のヒープに move するが, このとき元々の辺 $(u, v)$ を passive_list[$v$] に保存しておいて, サイクルを圧縮するときに passive_list に属する辺 $(u, v)$ について "$(u, v)$ のコスト + ($v$ の change cost)" と出発頂点 $u$ が属するヒープのキー値を比較して小さい方のみ考えるということをすると保持すべき $1$ つの辺を効率よく見つけることができる.
実際各辺は終端頂点 $v$ を見ているときにのみ辿られ, またその際に $1$ 度 passive_list に入った辺は後にまた passive_list に入ることもなく, サイクル併合時に $1$ 度見られてすぐ passive_list から削除されるので結局全体で辺を見るのにかかる計算量は $\O (m)$ となる.
(ポイント 4)
Union Find の根を自由に取れないことで特に最小全域有向木を復元するのが難しくなる(自分がうまい復元方法を思いついてないだけかもしれないが...). 経路圧縮だけで $y$ 回の Find 操作, $x - 1$ 回の Union 操作からなる任意の操作列について $y$ が $\Omega(x \log x)$ なら総計算量 $\O (y)$ みたいなこと言えないかなと考えてみたもののうまく言えそうになく, "Worst-Case Analysis of Set Union Algorithms" [Tarjan, LEEUWEN 1984] に解析が載っているのを見つけ, これによると $m \ge n$ について $\O (m \log_{\lfloor 1 + m / n \rfloor} n)$ らしくまたこれはタイトであるらしい(険しい). 正確には $m = \Omega(n \log n)$ について $\O(m \log_{\lfloor 1 + m / n \rfloor} n)$ がタイトであることが言えて初めて上記の予想が偽であることがわかるのだが, 解析をちゃんと読んでないがたぶん予想は偽っぽい.
つまるところ計算量のオーダーを変えずに根を自由に取るのは厳しく, 以下の実装では通常の計算は併合の工夫と経路圧縮の両方を用いた Union Find を用いて, 復元のためだけに超頂点を導入して頂点が縮約される関係を木構造で表現し, それを復元時にのみ用いることで $\O(n \log n + m)$ time で最小全域有向木の復元も含めて行うことができるようにしている. ただ実装が少々わかりにくくなってしまう & めんどくさくなる.

結局以上の議論よりアルゴリズムは $\O(n \log n + m)$ time であることが言える.