直径の1.5近似アルゴリズム

概要

$n$頂点$m$辺グラフの直径の1.5近似を$\tilde{O}(m\sqrt{n}+n^2)$時間で計算するAingworthら[1]のアルゴリズムを紹介します ($\tilde{O}(\cdot)$は$\mathrm{polylog}(n)$ factorを無視). 次にこのアルゴリズムの計算時間を改良したRoditty and Williams[2]による$\tilde{O}(m\sqrt{n})$時間乱択アルゴリズムを紹介します.

1. 導入

重みなし無向グラフ $G=(V,E)$ に対し二頂点$u,v$間の距離 $\mathrm{dist}(u,v)$ を最短経路長とします. このとき, $G$の直径 $\mathrm{diam}(G)$ は $\mathrm{diam}(G):=\max_{u,v\in V}\mathrm{dist}(u,v)$ で定義されます.

本記事のトピックは$n$頂点$m$辺グラフ$G$が与えられた時にその直径$\mathrm{diam}(G)$を計算する問題の計算量です. なお, 計算モデルは$O(\log n)$-word RAMを仮定します.

各頂点からBFSをすることによって$O(mn)$時間で計算することができます. 従ってこれよりも高速に計算できるかが焦点になります.

グラフの直径の計算は精緻な計算量(fine-grained complexity)においてかなり活発に議論されているトピックで, 直径3以下のグラフが与えられた時にその直径が$2$であるか$3$であるかを$O(m^{2-\epsilon})$時間で判別することはSETHと呼ばれる仮定の下では不可能であることが証明されています ($\epsilon>0$は任意の定数)[2]. すなわち, SETHを仮定すると直径の1.49近似を$O(m^{2-\epsilon})$時間で計算できないので, 例えば疎なグラフ ($m=O(n)$) では各点BFSによる$O(n^2)$時間アルゴリズムが最適であることを意味します. ここで, 直径の$c$近似 ($c>1$) というのは直径の$1/c$倍以上の値を出力することを意味します (例えば最大カットなどの文脈では$c^{-1}$近似の言い回しをよく使いますが, 直径近似研究の文脈では$c$近似と言うことが多く, 本記事もそれにならいます). ですので1.49近似アルゴリズムがあれば, 直径3のグラフに対してそのアルゴリズムを走らせると出力値は$\geq 3/1.49>2$となるため, 直径2と直径3のグラフを区別することができます.

それでは, SETHの下での近似困難性はタイトなのでしょうか? 具体的には, 疎なグラフに対し$O(n^{1.99})$時間で直径の1.5近似が計算できるかどうかが気になります. 

まず, 与えられるグラフ$G$が木である場合を考えてみます. このときはよく知られたdouble sweepと呼ばれる方法を使えば$O(m)$時間で直径の厳密値を計算できます. また, 一般グラフに対して適用すると, 直径の2近似が$O(m)$時間で計算できます.

本記事ではまず, Aingworthら[1]による$\tilde{O}(m\sqrt{n}+n^2)$時間で直径の"ほぼ"1.5近似を計算するアルゴリズムを紹介します. 具体的には彼らのアルゴリズムは $\lfloor 2/3 \mathrm{diam}(G) \rfloor \leq D \leq \mathrm{diam}(G)$を満たす値$D$を出力します. なお, 乱択を許しちょっと修正することによってAingworthらのアルゴリズムと同じ条件を満たす値$D$を$\tilde{O}(m\sqrt{n})$時間で出力する乱択アルゴリズムが知られています[2].

2. Aingworthらのアルゴリズム

Aingworthらによるアルゴリズム[1]を紹介します. double sweepを知っておくと感覚を若干ながら掴みやすいかもしれませんが, 知らなくても大丈夫です. また, 以下の説明ではBFSが出てきますが, これをDijkstra法に置き換えるとweighted graphに対して良い感じで動くと思うのですが, 私はあまり深く考えたことがないのでこの記事では割愛します. 以下, $O(m+n)$と書くのが面倒なので, $m\geq n$を仮定し, 単一始点BFSの時間計算量は$O(m)$と書いていきます.

アルゴリズム

1. 各頂点$v\in V$に対しBFSを行い$v$に近い順に頂点を$\sqrt{n}$個選び$S_v$とする (BFSを行い$\sqrt{n}$個の頂点に訪問したら途中で打ち切るようにする). なお, $v\in S_v$とする.

2. ステップ1で得られた集合族$(S_v)_{v\in V}$に対し, サイズ$O(\sqrt{n}\log n)$の hitting set $H\subseteq V$ を計算する (つまり, $H$は全ての$v\in V$に対し$H\cap S_v\neq\emptyset$を満たし, かつ$|H|=O(\sqrt{n}\log n)$を満たす集合. 存在性は後で示します).

3. $H$の各頂点$h\in H$に対し, $h$を始点としたBFSを行い, 全ての$h\in H,v\in V$に対し$\mathrm{dist}(h,v)$を計算する. その後, $D_1:= \max_{h\in H,v\in V}\mathrm{dist}(h,v)$とする.

4. $H$から最も遠い頂点を$u$とする. つまり$u$は$\min_{h\in H}\mathrm{dist}(h,v)$を最大にする$v$である.

5. ステップ4で得られた頂点$u$に対し, 各$x\in S_u$を始点としてそれぞれBFSを行い, 得られた距離の中での最大値を$D_2$とする. すなわち, $D_2:= \max_{x\in S_u,v\in V}\mathrm{dist}(x,v)$. 最後に$\max\{D_1,D_2\}$を出力.

計算時間:

- ステップ1では各頂点に対してBFSを行うので, 各$v\in V$に対し$O(|E(G[S_v])|)=O(n)$時間かかるので計$O(n^2)$時間です.

- ステップ2を考えます. まず存在性を議論します. 各頂点を独立に確率$q:=\frac{2\log n}{\sqrt{n}}$で選んで得られるランダムな頂点部分集合を$R$とします. このとき$\mathrm{E}[|R|]=2\sqrt{n}\log n$であって, Chernoff boundにより$|R|$は高確率 (具体的には確率$1-n^{-1}$で) $|R|=O(\sqrt{n}\log n)$となります. また, 固定した頂点$v\in V$に対して「$S_v$の全ての頂点が選ばれない」確率は

$(1-q)^{|S_v|}\leq \exp(-q|S_v|)=\exp(-2\log n)=n^{-2}$

なので, 確率$1-n^{-2}$で$R$は$S_v$の頂点を一つ以上含みます. 従って, union boundにより確率$1-1/n$で$R$は hitting set になっています. 以上より, $R$は高確率でサイズ$O(\sqrt{n}\log n)$の hitting set になってます. もし条件を満たすhitting setが存在しないならばこの確率は$0$にならなければいけないので, 存在性を示せたことになります. また, ランダムにとってくればほぼ確実に条件を満たすhitting setになっているので, 乱択を許せば$O(n)$時間でステップ2を計算できます. また, greedyにやれば ($H=\emptyset$からスタートして$S_{v_1}$の頂点を一つ選んで$H$に追加し, 暫定の$H$がhitしていないような$S_{v_2}$を選んで...を繰り返す) 条件を満たすようにできます.

-ステップ3は$O(|H|m)=O(m\sqrt{n}\log n)$時間で計算できます.

-ステップ4はステップ3の情報を使えば計算できます.

-ステップ5は単一始点BFSを$\sqrt{n}$回行うので$O(m\sqrt{n})$時間で計算できます.

以上より, 全体の時間計算量は$O(m\sqrt{n}\log n+n^2)=\tilde{O}(m\sqrt{n}+n^2)$です.

近似率の解析

アルゴリズムの出力を$D=\max\{D_1,D_2\}$とします. 単純のため, $\mathrm{diam}(G)$は3の倍数とします. 直径を達成する二頂点を$a,b\in V$とします (つまり$\mathrm{dist}(a,b)=\mathrm{diam}(G)$).

二つのケースを考えます:

(1). ある $h\in H$, $v\in V$ が存在して $\mathrm{dist}(h,v)\geq \frac{2}{3}\mathrm{diam}$ がなりたつならば, $D_1$が直径の1.5近似になっているので大丈夫です.

(2). 全ての$h\in H$, $v\in V$に対して $\mathrm{dist}(h,v)<\frac{2}{3}\mathrm{diam}$が成り立つとします. ステップ4で計算した頂点$u$に対し, $\ell:=\min_{h\in H}\mathrm{dist}(u,h)$とすると, $u$の定義より任意の$v\in V$は距離$\leq\ell$で$H$内のいずれかの頂点にたどり着くことができます. ここで$\mathrm{dist}(a,h)\leq \ell$を満たす頂点$h\in H$をとります. すると三角不等式より

$\mathrm{diam}\leq\mathrm{dist}(a,h)+\mathrm{dist}(h,b)<\ell+\frac{2}{3}\mathrm{diam}$,

すなわち $\ell>\frac{\mathrm{diam}}{3}$ を得ます (下図). また, $H$ は $(S_v)_{v\in V}$の hitting set であるため, 特に $H \cap S_u \neq \emptyset$ です. 従って (*)$u$ から距離$\leq\frac{\mathrm{diam}}{3}$ なる頂点は全て$S_u$に属しているはずです (行間補足: $S_u$ は $u$から近い順に頂点を取っていて, 距離$\ell>\frac{\mathrm{diam}}{3}$ だけ離れている頂点 ($H$との共通部分) も取っているのでそれより近い頂点は全て$S_u$に入っていなければならない).

ここで, $D_2 < \frac{2}{3}\mathrm{diam}$と仮定します. このとき, $D_2$の定義より, 全ての頂点は$u$から距離$<\frac{2}{3}\mathrm{diam}$となっています. 次に, $\mathrm{diam}=\mathrm{dist}(a,b)\leq \mathrm{dist}(a,u)+\mathrm{dist}(u,b) < \mathrm{dist}(a,u)+\frac{2}{3}\mathrm{diam}$ より, まとめると $\frac{1}{3}\mathrm{diam}<\mathrm{dist}(u,a) < \frac{2}{3}\mathrm{diam}$ を得ます.

最短$ua$経路上の頂点であって, $u$からの距離がちょうど$\mathrm{diam}/3$となる頂点を$p$とします. $\mathrm{dist}(a,u)=\mathrm{dist}(a,p)+\mathrm{dist}(p,u)<\frac{2}{3}\mathrm{diam}$となるため, $\mathrm{dist}(a,p)<\frac{1}{3}\mathrm{diam}$です. さらに, $p$の取り方から主張(*)より, $p\in S_u$です.

三角不等式より,

$$\mathrm{diam}=\mathrm{dist}(a,b)\leq \mathrm{dist}(a,p)+\mathrm{dist}(p,b)<\mathrm{dist}(p,b)+\frac{1}{3}\mathrm{diam}$$

よって, $D_2\geq \mathrm{dist}(p,b) > \frac{2}{3}\mathrm{diam}$ となってしまい仮定に矛盾します. よって$D_2\geq \frac{2}{3}\mathrm{diam}$ となります (証明終).

ちょっとした改善

最後に, Roditty と Williams [2] がによるちょっとした改善を紹介します. 基本は上記のAingworthらのアルゴリズムと同じですが計算時間を$\tilde{O}(m\sqrt{n}+n^2)$ から $\tilde{O}(m\sqrt{n})$にしています. つまりグラフが疎であれば高速になります.

アイデアは単純で, ステップ1を行わず, ステップ2で得られた hitting set $H$ を, 全頂点を独立に確率$2\log n/\sqrt{n}$で選んで得られるランダムな頂点部分集合とします. そしてステップ5では$u$に対して$S_u$を計算するだけです. Aingworthらのアルゴリズムではステップ1の計算で$O(n^2)$時間がかかっていましたが, そもそも$H$が $(S_v)_{v\in V}$ の hitting setであれば良いだけなので, 計算時間の解析でも紹介したようにランダムにとるだけで良いので省くことができます.

感想

賢すぎて草

参考文献

[1] D. Aingworth, C. Chekuri, P. Indyk, and R. Motwani. Fast estimation of diameter and shortest paths (without matrix multiplication). SIAM J. Comput., 28(4):1167–1181, 1999 (Preliminary version is in SODA96).

[2] L. Roditty and V. V. Williams, Fast Approximation Algorithms for the Diameter and Radius of Sparse Graphs, STOC13.