STA Chapter2 part2

Sublinear Time Algorithms

Estimating the Number of Connected Components

Connected Components(連結成分,以下c.cと書く)
  • c.c内の任意の二点間を結ぶパスが存在する。
  • 異なるc.c間にはいかなるパスも存在しない。

問題設定

入力
  • 無向グラフG(V,E)
  • 制限 \led
目標

c.cの数をcとしたとき、εd-additiveとは見積もった数yが、
c - \epsilon n \le y \le c + \epsilon n
をみたすこと。

文字の定義および、整理

n_{u}をuに含まれるc.cのノードの数とする。
このとき、任意のc.c　A ⊆ Vに関して
\sum_{u \in A} \frac{1}{n_{u}} = \sum_{u \in A} \frac{1}{|A|} = 1
また、
c = \sum_{u \in V} \frac{1}{n_{u}}
\hat{n}_{u} = \mathrm{min} \left{ n_{u} \: , \: \frac{2}{\epsilon} \right} \; , \; \hat{c} = \sum_{u \in V} \frac{1}{\hat{n}_{u}
とすると、
| \frac{1}{n_{u}} - \frac{1}{\hat{n}_{u}} | \le \frac{2}{\epsilon}
となる。
\hat{n}_{u} = n_{u}のときは0、\hat{n}_{u} = \frac{2}{\epsilon}のとき、\frac{2}{\epsilon} < n_{u} \leftrightarrow \frac{\epsilon}{2} - \frac{1}{n_{u}} > 0
これより、シグマをとって
| c - \hat{c} | \le \frac{\epsilon n}{2}

アルゴリズム

estimate_cc(u)

　uからBFS(幅優先探索)を走らせる。
　　c.c全体を見つける
　　2/ε個の異なるノードを見つける
　いずれかを満たしたらノードの数を出力する。
estimate_cc(u)の計算時間
O \left( \frac{d}{\epsilon} \right)
各ノードから出るエッジの数はせいぜいdであるため。

approx_num_cc(G,ε)

　 U = \left{ u_{1}, u_{2}, \ldots , u_{r} \right} , r = \Theta \left( \frac{1}{\epsilon~{3}} \right) で集合Ｕを選ぶ
　各u∈Uに関して、estimate_cc(u)を用い、\hat{n}_{u}を求める。
　\tilde{c} = \frac{n}{r}\sum_{n \in U}\frac{1}{\hat{n}_{u}}を出力
approx_num_cc(G,ε)の計算時間
O \left( \frac{1}{\epsilon^{3}}\frac{d}{\epsilon} \right) = O \left( \frac{d}{\epsilon^{4} \right)

Pr \left( | \tilde{c} - \hat{c} | \le \frac{\epsilon n}{2} \right) \ge \frac{3}{4}の証明

Chernoff boundにおいて
p = E \left[ \frac{1}{\hat{n}_{ui} \right] ,\; S = \sum_{i=1}^{r}\frac{1}{\hat{n}_{ui}} , \; m=r, \; \delta = \frac{\epsilon}{2}とおく、
\tilde{c} = \frac{n}{r}\sum_{n \in U}\frac{1}{\hat{n}_{u}} ,\; E \left[ \frac{1}{\hat{n}_{ui}} \right] = \frac{1}{n}\sum_{i=1}^{n} \frac{1}{\hat{n}_{ui}} = \frac{\hat{c}}{n} ,\; r = \Theta \left( \frac{1}{\epsilon^{3}} \right)
であることに注意すると、
Pr \left( | \frac{1}{r} \sum_{i=1}^{r} \frac{1}{\hat{n}_{ui}} - E \left[ \frac{1}{\hat{n}_{ui} \right] | \ge \frac{\epsilon}{2} E \left[ \frac{1}{\hat{n}_{ui}} \right] \right) \le \exp{ \left( -\Omega \left( rE \left[ \frac{1}{\hat{n}_{ui}} \right] \left( \frac{\epsilon}{2}p \right) \right) \right) }
Pr \left( | \frac{\tilde{c}}{n} - \frac{\hat{c}}{n} | \ge \frac{\epsilon}{2} \frac{\hat{c}}{n} \right) = Pr \left( | \frac{\tilde{c}}{n} - \frac{\hat{c}}{n} | \ge \frac{\epsilon\hat{c}}{2} \right) \le \exp{ \left( - \Omega \left( r \frac{\hat{c}}{n} \left( \frac{\epsilon}{2} \right)^{2} \right) \right) } =\exp{ \left( - \Omega \left( \frac{1}{\epsilon}\frac{\hat{c}}{n} \right) \right) }
定義より、
\frac{\epsilon}{2} \le \frac{1}{\hat{n}_{u}} \le 1 , \; \frac{\epsilon n}{2} \le \hat{c} \le n
よって、
Pr \left( | \tilde{c} - \hat{c} | \ge \frac{\epsilon n}{2} \right) \ge exp{ \left( - \Omega \left( 1 \right) \right) } < \frac{1}{4}
ここで、
| c - \hat{c} | \le \frac{\epsilon n}{2} , | c - \hat{c} | \le |c-\hat{c}| + |\tilde{c} - \hat{c}|より
Pr \left( | c - \tilde{c} | \le \epsilon n \right) = Pr \left( | \tilde{c} - \hat{c} | \le \frac{\epsilon n}{2} \right) \ge \frac{3}{4}