グラフの直径とは
D:=\max_{u,v\in V} \mathrm{dist}(u,v)
によって定義される量です. こちらの記事ではその計算量の歴史について触れましたが, 今回は直径に対する高速な近似アルゴリズムについて具体的に紹介します. 連結な重み無し無向グラフ$G=(V,E)$の直径$D$が知りたいとします. 二頂点$u,v$間の最短経路長を省略して$uv$と書くことにします.
Double sweep
1.頂点 $u$ 適当にとってくる.
2.$u$ を開始点としたBFSにより, 最も遠い頂点 $f_1$ を得る.
3.同様に $f_1$ から最も遠い頂点 $f_2$ を得る.
4. $f_1f_2$ を出力.
Claim: $0.5D \leq f_1f_2\leq D$ (つまり $f_1f_2$ は 2-近似).
Proof: 観察として, 以下がわかります:
- 任意の頂点 $x$ に対し, $ux\leq uf_1$ ( $f_1$ の定義より明らか).
- 任意の頂点 $x$ に対し, $xf_1 \leq f_1f_2$ ( $f_2$ の定義より明らか).
グラフ上の最短経路長は三角不等式を満たすので, 任意の二頂点 $x,y$に対して
$xy \leq xu+yu \leq 2uf_1 \leq 2f_1f_2$.
今, $x$ と $y$は任意だったので, 直径の両端点となるようにとれば
$f_1f_2 \leq D \leq 2f_1f_2$. (証明終)
Claim: 木 $T$ を入力としたとき, double sweepは直径のexactな値を出力する. すなわち, 任意の二頂点 $x,y$ に対し, $xy\leq f_1f_2$.
$T$ を $u$ を根とした根付き木とする. $f_1$ と $f_2$ のLCA(least common ancestor)を $v$ とおく. 最後に, 二頂点$s,t$を結ぶ $T$ 上のパスを $P(s,t)$ と書くことにする. まず, 以下に述べるobservationを示す.
Observation. 任意の頂点 $x$ に対して
(i). $v\in P(u,x)$ ならば $vx \leq vf_1$.
(ii). $v \not\in P(u,x)$ ならば $vx \leq vf_2$ ($\leq vf_1$).
Proof of Observation:
(i): そうでないと仮定すると, $ux=uv+vx>uv+vf_1=uf_1$ となり, $f_1$ が $u$ から最も遠いという仮定に矛盾.
(ii): そうでないとすると, $f_1x=f_1v+vx > f_1v + vf_2=f_1f_2$ となり, $f_2$ が $f_1$ から最も遠いという仮定に矛盾.
Proof of Claim: 任意に二頂点 $x,y$ をとる.
1): $vx \leq vf_2$ とする. このとき, グラフ上の三角不等式より
$xy \leq xv+xy \leq vf_2+vf_1=f_1f_2$.
2): $vx>vf_2, vy>vf_2$ とする. このとき, $P(f1,x)$ は $v$ を含まない. なぜならそうでないとすると, $f_1x=f_1v+vx>f_1v+f_2v=f_1f_2$ となり矛盾するからである. $y$ に対しても同様の議論が成り立つ. $x$ と $f_1$ の lca を $w$ とおく. このとき,
$xy\leq xw+wy \leq f_1w+wy=f_1y\leq f_1f_2$
となる.
ここで, ２番目の不等式は, $w$ は $f_1$ と $x$ の共通祖先であり, $v\in P(u,x)$ および $v\not\in P(f_1,x)$ より $w$ は $v$ の子孫であるため,
$f_1u=uw+wf_1\geq ux=uw+wx$であることから成り立つ.
(証明終)
Random Sampling
- $D'\gets 0$ とする.
- 頂点 $u$ を $V$ 上の一様分布に従って選ぶ.
- $u$ から最も遠い頂点 $f$ を計算し, $D'\gets \max(D', uf)$ で更新する.
- ステップ1から3を $\lceil 100n^{1-\delta}\log n\rceil$ 回繰り返す.
- $D'$ を出力する.
*Claim: 定数 $\delta>0$ に対し, 直径 $D$ が $D\geq n^{\delta}$ を満たすとします. このとき, 任意の $\epsilon>0$ に対して上記アルゴリズムは $O(mn^{1-\delta}/\epsilon)$ 時間で $D'$ を出力し, $D'$は $1-n^{-50}$ 以上の確率で$\frac{D}{1+\epsilon}\leq D' \leq D$ を満たす (つまり $D'$ は $(1+\epsilon)$-近似). *
Proof: double sweepが2-近似を達成するので, $\epsilon$ は1未満とします. 二頂点 $a,b$ を直径の両端点 (即ち $ab=D$ ) とします. このとき, $ab$-間の最短経路上には $a$ との距離が $\frac{D}{1+\epsilon}$ 以上であるような点が $\frac{\epsilon}{1+\epsilon}D$ 個以上あります. 従って, ランダムに選んだ $u$ に対して
$\Pr\left(au < \frac{D}{1+\epsilon}\right)\leq 1-\frac{\epsilon D}{(1+\epsilon)n} \leq 1-\frac{\epsilon}{2}n^{-1+\delta} \leq \exp(0.5\epsilon n^{-1+\delta})$
が成り立ちます.
ランダムに $u$ を選ぶプロセスを $100 n^{1-\delta}\log n$ 回以上繰り返すので, アルゴリズムの出力が $(1+\epsilon)$-近似にならない確率は高々
$ \exp(0.5\epsilon n^{-1+\delta}\cdot 100n^{1-\delta}\log n)=n^{-50}$
となります. (証明終)
結びに
他にも面白い近似アルゴリズムが知られています. 特に私のお気に入りは Aingworth et al. (1996) の "ほぼ1.5-近似" アルゴリズムですが, またの機会に紹介したいと思います.