S(n)-separable graphs

S(n)-separable graphs
今日は先日まとめた任意のアスペクトレシオの最適面積長方形への完全二分木の埋め込みアルゴリズムを全二分木に拡張するのに有用だと思われる。
分割子を用いたグラフの再帰的な埋め込み方について。埋め込みとは格子点に頂点を格子中のパスを辺に対応させるものである。辺は同じ格子辺を定数回であれば重なっても良いものとする。

分割子を使った埋め込み
この分割統治を使ったアルゴリズムでは与えられたグラフから少数の辺を取り除き分割された２つのグラフを埋め込みをの間に取り除いた辺を取り除くというものである。よって非常に密なグラフ（極端な例で言えば完全グラフの族）にたいしてはこの方法は効率よく働かない。

Definition: Graph class C は S(n)-separableである
1.C内の任意のグラフG( |G|≧2 )についてサイズが高々S(n)の辺集合を見つけることができて、その集合を取り除くことによってＧを２つの互いに日連結な部分グラフG1,G2に分割できてG1,G2の接点数をそれぞれn1,n2とするとn1≧n/3かn2≧n/3が成り立つ。したがって、どちらの部分グラフも互いに他の部分グラフの２倍より多くの接点数をもたない
2.G1,G2はCの要素

よってグラフ族CがS(n)-separableであるとは、Ｃの任意のグラフは階層的にどこまでもS(n)本の辺を取り除くことで分割できるというものである。

例3.2　２分木の族は1分割可能である。
(証明）ある２分木Tにおいて、任意に次数２の点を根rとする。rの両方の子の子孫のうち、n/3以上2n/3以下の子sがあれば(r,s)をカットして終了。そうでなければ2n/3以上の子孫を持つ子tが存在するので、そのtを根とする部分木を対象に上の操作をおこなう。２分木の中の１本の辺だけをカットするので残ったグラフG1,G2もまた２分木である（証明終）


強分割子
紹介する分割統治法を使用するためには１：２では使えない。１：１になるように拡張する必要がある。あるグラフ族が強S(n)分割可能であるとは

Definition: Graph Class C はstrongly S(n)-separable
1.C内の任意のグラフG( |G|≧2 )についてサイズが高々S(n)の辺集合を見つけることができて、その集合を取り除くことによってＧを２つの互いに日連結な部分グラフG1,G2に分割できてG1,G2の節点数が高々(n+1)/2である。
2.G1,G2はCの要素

この強分割子について以下の定理が成立する。

Thm. If Graph Class C is S(n)-separable, then C is strongly Γs(n)-separable.where Γs(n)=S(n)+S(2n/3)+S(4n/9)+...(ceil(log_{2/3}n)項)
（証明）グラフGに対する分割木を考える。分割木とはGがひとつの頂点からなる場合は葉ひとつからなる木になり、GがG1,G2に分割できる場合はGを根としG1,G2の分割木をそれぞれの部分木とする２分木である。
ここではこの定理よりも強い結果を示す。Gの接点数より少ない任意の目標接点数tに対してGをあらわす根からある葉までの経路が存在して、その経路上の節点のある兄弟のいくつかの和集合のグラフがGのt子の接点を含む部分グラフをあらわすようにできることを示す

分割木の高さの帰納法による。
高さが０の場合、分割木が１頂点からなり、t=0にしかならないのでＯＫ
帰納段階で根の左と右の子がそれぞれn1,n2個の節点を持つとする。n1≦tならば
経路は右に降りて目標値をt-n1と更新する。このとき左の子を選出集合に入れる。
相でない場合、n1＞tかつn2≦tの場合は経路は左に下りて目標値t-n2とする。このとき選出集合には右の子を追加する。最後にどちらともtを超える場合はどちらかに降りるだけでよい。

Gの分割木Tに対してできた経路をv0,v1,...,vkとして選出集合をu_a0,u_a1,...,u_ak'とする
このGはS(n)分割可能なので各経路で選ばれた選出集合u_ai とそれを選出集合に含めたときの根vaiは高々S(n)本の辺でつながっている。そして、vaiのサイズは(2/3)^inなので
S(n)+S(2n/3)+S(4n/9)+...
を超えない。（証明終）

この定理ではかなり大まかに上界を算出している。全２分木の場合はどうなるのかを考える必要がある。これは明日以降。

Mixing Markov Chains(4)

前回以前の内容は私のもうひとつのweblogであるMileStones to EVERPEACEのIX-th stoneまでに載っているのでそちらを参照

前回n-Cube中のランダムウォークを定義したが、そのランダムウォークのCoupling Timeを算出しよう。任意の２状態 X0,Y0から始まって同時に(i,b)のペアによってX,Yを更新していくことを考える。

XとYが同じになるのは、全ビットが少なくとも１度変更されるよりも前に起こる。前回のCoupon Collecting問題に当てはめてみると(i,b)の組の半分を集める時間よりも前にX,Yがcoupleすることになる。よってMCcのcoupling timeはO(nlog n).

よってThm4.によって、次の定理が導ける。

Thm5. The Markov Chain MCc has mixing time τ(ε)=O(n ln(nε^{-1}))

Couplingでは任意の２状態からのcoupling　time を算出する必要があるが、次に紹介するPath Couplingでは、Ω×Ω全体ではなくその部分集合Uの２を考えればMixing Timeが求まるというものである。

Path Coupling
Couplingでは任意の２状態を対象にしなければならなかったが、このpath couplingでは距離関数φによって比較的近い２状態を対象にすればよいものである。そしてその距離関数をもとにMixing Timeを算出するものである。
U⊆Ω×Ωを考える（パスの集合）任意の２状態X,YについてX=z0,z1,z2,...,zr=YというU内に属するパスだけを使って常に最短距離になるようなＵを見つけたとする。すると、
φ(X,Y)=sum(φ(zi,zi+1))
と常に表現できる。期待値の線形性より、U内のパスに対してのみtransition数の期待値を考えれば、その和で任意の状態間のtransition数の期待値がわかるというのがメインアイデアである。
このpath set Uを使って以下の定理が証明されている。

Thm6. φをΩ×Ω→{0,...,B}なる距離関数とする。UをΩ×Ωの以下を満たす部分集合とする。
任意の(xt,yt)∈Ω×Ωに対してU内の要素からなる最短パスを作ることができる。
そして、MをPを遷移行列とするΩ上のMarkov chainとし、f:Ω→ΩをP[f(x)=y]=P(x,y)となるランダム関数とする。
そしてこのMのcouplingを(xt,yt)→(xt+1,yt+1)=(f(xt),f(yt)).すると以下が成り立つ
1.If there exists β＜1 s.t. E[φ(xt+1,yt+1)]≦βφ(xt,yt) for all (xt,yt)∈U, then mixing time τ(ε)≦ln (Bε^{-1})/(1-β)
2.If β=1 ( i.e. E[Δφ(xt,yt)]≦0 for all xt,yt∈U), let α satisfy Pr[φ(xt+1,yt+1)≠(xt,yt)]≧α for all xt,yt(xt≠yt), then mixing time　τ(ε)≦ceil(eB^2/α)ceil(ln ε^{-1})

次回はこの定理を応用して与えられたグラフのcoloringの数を算出してみたい。