STA Chapter2 part3 - nsasakiの勉強メモ

Estimating the Weight of the Minimum Spanning Tree

Spanning Tree(以下st)

あるグラフの全ての頂点とそのグラフを構成する辺の一部分のみで構成される木のこと

問題設定

入力

無向グラフG(V,E)
制限 $\le$ d
各エッジ(i,j)は整数の重み $w_{ij} \in \left[ w \right] \cup \left{ \infty \right}$ をもつ隣接知ると出グラフを与えられウエイト∞のエッジは現れない。

目的

Gのstのウエイト総和が最小となること(以下、この状況のことをMSTと呼ぶ)
$w \left( T \right) = \Sigma_{(i,j) \in T} w_{ij}\; \; T \subseteq E$
$M = \min_{T \text{ spans } G} w \left( T \right)$
とすると、
$\left( 1 - \epsilon \right) M \le \hat{M} \le \left( 1 + \epsilon \right)$
となる $\hat{M}$ をもとめる。

※
$n -1 \le M \le w \left( n -1 \right) \; , \; n = |V|$
となる。
理由はn-1本のエッジを選べばstができるため、かつ各エッジのウエイトは1〜wであるため。

From motivation to characterization

$G^{\left( i \right) } = \left( V , E^{ \left( i \right) } \right)$ はGのサブグラフでウエイトがi以下
$C^{\left( i \right) }$ を $G^{\left( i \right) }$ におけるc.cの数
とする。

A motivation

単純なケース

w = 1のとき
M = n-1
w = 2のとき
$G^{\left( 1 \right) }$ にはウエイト2の $C^{\left( 1 \right) } - 1$ 本のエッジを
$G^{\left( 1 \right) }$ のc.cにつなげばよい。
すなわち、
$2 - \left( C^{\left( 1 \right) } - 1 \right) + 1 \left( n - 1 - \left( C^{\left( 1 \right) } - 1 \right) \right) = n - 2 + C^{\left( 1 \right) }$

w=nへの一般化

$M = n - w + \sum_{i=1}^{w-1} C^{\left( i \right) }$
となる。

証明

GのMSTにおけるウエイトiのエッジの数を $\alpha_{i}$ とする。
ウエイトl以上のエッジの数は $C^{\left( l \right) } -1$ である。
$\therefore \sum_{i = l+1}^{w} \alpha_{i} = C^{\left( l \right) } - 1$
$C^{\left( 0 \right) } = n$
であることより、
$\begin{align} M & = & \sum_{i=1}^{w} i \alpha_{i} \\ & = & \sum_{i=1}^{w}\alpha_{i} + \sum_{i=2}^{w}\alpha_{i} + \cdots + \alpha_{w} \\ & = & \left( n - 1 \right) + \left( C^{\left( 1 \right) } - 1 \right) + \cdots + \left( C^{\left( w-1 \right) } - 1 \right) \\ & = & n - w + \sum_{i=1}^{w-1} C^{\left( i \right) } \end{align}$

Approximation algorithm

MST_approx(G,ε,w)
iからw-1まで
　 $\hat{C}^{ \left( i \right) } = \mathrm{approx \: num \: cc} \left( \hat{G}^{ \left( i \right) } , \frac{\epsilon}{2w} \right)$ *1
最後に、
$\hat{M} = n - w + \sum_{i=1}^{w-1} \hat{C}^{\left( i \right) }$
を出力

各approx_num_ccにかかる計算時間は
$O \left( \frac{d}{ \left( \frac{\epsilon}{2w} \right)^{4} } \right) = O \left( \frac{dw^{4}}{\epsilon}^{4} \right)$
これをw-1回繰り返すため
$O \left( \frac{dw^{5}}{\epsilon^{4}} \right)$
approx_num_ccに関してウエイトi以上のエッジは無視するようにすればよい
$| \hat{C}^{ \left( i \right) } - C^{ \left( i \right) } | \le \frac{n\epsilon}{2w}$
が高確率で成功、各iについてそうであるため
$| \hat{M} - M| = | \sum_{i=1}^{w-1}{\hat{C}^{ \left( i \right) } - \sum_{i=1}^{w-1}C^{ \left( i \right) } | \le \sum_{i=1}^{w-1} |\hat{C}^{ \left( i \right) } - C^{ \left( i \right) } | \le \frac{n \epsilon}{2w} \left( w - 1 \right) \le \frac{n \epsilon}{2w}\left( w \right) = \frac{n \epsilon}{2}$
$n \ge 2$ において、 $\frac{n}{2} \le n -1$ が成立。
また $n - 1 \le M$ である。以上より、
$| M - \hat{M} | \le \frac{n}{2} \epsilon \le M \epsilon$
となる。
現在、 $\Omega \left( \frac{dw}{\epsilon^{2}} \right) , O \left( \frac{dw}{\epsilon^{2} } \log{ \left( \frac{dw}{\epsilon} \right) } \right)$ のアルゴリズムが知られている。