STA Chapter1 part3

Sublinear Time Algorithms

Graph connectivity

入力：　G = (V,E), n = |V| , m = |E| , bounded degree d*1 グラフはn×dの隣接行列で与えられる
目的：　グラフが連結グラフか？

目的を以下のように変更する

Gが連結性にε-closeとは、Gを連結するのに高々εdn本の枝を足せばよいことを言う。

作りたいアルゴリズム*2
  • if Gが連結 then accept 1
  • if Gがε-far-from 連結 then reject 3/4

アルゴリズム

  1. O(1/εd)のノード(頂点)をランダムに選ぶ。
  2. 各ノードsに関して幅優先探索を行う
    1. \ge \frac{2}{\epsilon d}をみたすノードが見つかる
    2. sがサイズ \le \frac{2}{\epsilon d}の連結グラフ
  3. もし2.2が起きたらGをrejectして停止
  4. そうでなければaccept

O \left( \frac{1}{\epsilon d} \times \frac{2}{\epsilon d} \times d \right) = O \left( \frac{1}{\epsilon^{2} d} \right)

もし、Gがε-farならばGはεdnの連結成分*3を持つ.
もし、Gがεdn未満のc.cをもつならばGはε-close
ということになる。
すなわち、εdn-1本足すとGは連結にできる。

このことから、
Gは少なくとも \frac{\epsilon dn}{2}個でサイズは最大でも \frac{2}{\epsilon d}であるc.cをもつことになる。

もし、これが成り立たないと仮定すると
Gは少なくとも \frac{\epsilon dn}{2}個で \frac{2}{\epsilon d}以上のサイズであるc.cをもつ
これは、
頂点数　> \frac{\epsilon dn}{2} \times \frac{2}{\epsilon d} = nとなり矛盾。

Gが連結ならば、rejeectが起きないので100% accept
Gがε-far-fromならば、
\mathrm{Prob [ fail ]} \ge 1 - \mathrm{Prob [ pass ]} \ge 1 - {\left( 1 - \frac{\epsilon d}{2} \right) }^{O(1 / \epsilon d)} \ge 1 - e^{-c'} \ge \frac{3}{4}
となる。

*1:nもmもdより少ない

*2:このようなアルゴリズムをone-sided error algorithmという

*3:c.cと表記する