Circular Arc Coloring is pollynomially equivalent to The Word Problem for Products of Symmetric Group

以前、リング上のパス（arc)の色づけはconflict graphの形がかなり制限されることから、NP完全にはならないのではないかと予想したが、それについての証明。今回はタイトルの２つの問題が等価であることを証明する。

まず、基礎知識。リング上の２点を結ぶ無向パスを円弧（circular arc）と呼ぶ。そのarcに対して同じ色どうしの弧が重ならないように色づけをすることを考える。formal には次のとおり

ARCCOLORING:
INPUT: a family F of circular arcs and integer K
OUTPUT: can F be colored with K colors so that no two arcs in the same color?

これはFを頂点集合として、重なるarcどうしを辺で結んだグラフ（circular arc graph）における頂点彩色問題と考えることができる。

次にthe Word Problem of Products for Symmetric Groupという問題について。集合Ａ＝{1,...,K}からそれ自身への全単射は置換として考えられ、その置換全体は置換を合成することを演算として群を構成する。これを対称群(Symmetric Group)という。たとえば、f(k)=k+1を２回施すと、f²(A)={K-1,K,1,2,...,K-2}
となる。そしてこの問題はformalには

WPPSG:
INPUT: Integer K and X₁...X_m ⊆{1,...,K} and permutation π∈S_K
OUTPUT:does π belong to the set P=S_X1•...•S_Xm

すなわち、{1,...,K}とその部分集合の族（全」順序あり）、そしてKの順列があたえられたとき、部分集合ないの要素だけからなる置換を順番に適用していってπにできるかどうか？という問題である。

Thm. WPPSG is polynomially equivalent to ARCCOLORING
proof. WPPSG のインスタンスを受け取ってそれをARCCOLORINGのインスタンスにする。まず用意するリングのサイズはK+m. そしてi∈Aに対してiを含む部分集合の添え字をl_i[1],...,l_i[k(i)]としておく。そのとき各iに対して弧の集合F_iを次のように作る。

A_i,1=(i,K+l_i[1])
A_i,2=(K+l_i[1],K+l_i[2])
...
A_i,k(i)=(K+l_i[k(i)-1],K+l_i[k(i)])

とつくる。そしてつぎに

C_i=(K+l_i[k(i)],π^-1(i))

として

F=(∪Fi) ∪ (∪Ci)

とする。この変換は多項式時間でできるのは自明。あとはπ∈P⇔F is K-colorable を証明すればいい。そのためにK+m+1のサイズの弧の集合を考えてこれがK-colorableかどうかを議論する。そのために各C_iを次のように変更する

C_i←{(K+l_i[k(i)],K+m+1),(K+m+1,π^-1(i))}

そして、このようにしたものをF'とする。そしてF'_iを

F'_i=F_i∪{(K+l_i[k(i)],K+m+1),(K+m+1,i)}

とする。

こうして F'=(∪F'_i) ∪ (∪Ci)とする。このF'に対する任意のK-coloringはσ^p,p&isin {1,...,K+m+1}で書き表わせる。σ_p(j)はnode pにおいて色jがついている弧が含まれているF'iの添え字をあらわす。
一般性を失わずにσ₁(j)=jとできる。頂点1のについている色を基準にできるということである。すなわちF'iのすべての(K+m+1,i)は色iが代入されているとできるということである。そして(K+m+1,i)と、(i,K+l_i[1])は(K+m+1,k),k∈{i+1,...,K},and(k,K+l_k[1]),k∈{1,...,i-1} というK-1個の弧と交わっているので両者は同じ色を持たなくてはならない。よって2,...,K+1までの頂点においては頂点１上の色づけと同じでなくてはならない。

σ₁=σ₂=...=σ_K+1

ここでK+2での色づけはでS_X1の要素を施したものになる。よってK+m+1上の色づけはP=S_X1•...•S_Xmの要素になっている。

ここで、(K+m+1,i)は付け加えたようにみえるが、これらは(K+m+1,π^-1(i))としてF'_&pi^-1に含まれていたのである。そして、Ciはただ２つに分けられただけなのでそれらは同じ色がつけられるはずである。よって

σ^-1_K+m+1(i)=σ^-1₁(π^-1(i))

よってσ_K+m+1=π となるこれでWPPSGがARCCOLORINGに帰着できることがわかった。

あとは逆の手順を示す。
この場合の入力は整数Kと、family F of arcsである。ここで任意の頂点pはちょうどK個の弧でかspanされているとして一般性を失わない。なぜならKより多くの弧にspanされていたら、答えはnoで自明かつ多項式時間でチェック可能。そしてK未満の個数でしかspanされていない頂点pがあれば、(p-1,p)の形の弧ををK-k個追加することでできる。この操作ではK-colorablityは失われないので問題ない。

これ以降は次回

Mixing Markov Chains(5)

前回紹介したpath couplingの応用。与えられたグラフのk-coloring全体をカウントしてみたい。
そこで、Ω={1,...,k}^Vを状態空間全体とし、Ω上のMarkov chain　MCcolを定義する。

MCcol: starting t0, repeat t times:
1. With prob 1/2, do nothing.
2. Pick (v,c) ∈V×{1,...,k}
3. if v can be recolored with c, recolor it; otherwise do nothing.

このMCcolはergodicであることは容易にわかる。そこでHamming distanceが１である組全体を考える。それをUとしてpath couplingの定理を適用してみたい。

Thm. MCcol on k-colorings has mixing time τ(ε)=O(n ln(nε^{-1})) on any n-vertex graph with maximum degree d whenever k≧3d+1

（証明）path couplingを適用するためにHamming Distance 1のペア全体Uを考える。
すると任意の二状態x,y(Hamming(x,y)=l)に対して, x=z0,z1,z2,...,zl=yとなるパスがU上の辺で構築できる。そしてGの色数は最大次数を下界に持つ。そしてΩ上の距離関数φの値域は{0,,,B}(B≦2n)で十分である。
よってU内の２状態（ハミング距離１）のペアから始まるchainだけを考えればよくなった。formalには(r,s)∈U, E[Δφ(r,s)]を考える必要がある。状態r,sを一ステップ進めたときにpickされた頂点をvとし、(r,s)間で色の違っている頂点をwとする。

case1)w=v
この場合はランダムウォークのステップがr,sのとなった場合。この場合少なくともk-d色に変化する可能性がある。そして変更されれば,ハミング距離は必ず減る。よってE[Δφ(r,s)]≦-(k-d)/kn

case2)(w,v)∈E
w,vが隣接していた場合、変化できて距離が増えるのはvがrとs中のwの色のどちらかに変化する場合である。どちらが変化しても（どちら変化した場合も）ハミング距離は増える。その期待値はE[Δφ(r,s)]≦2/kn

case3)(w≠v) かつ (w,v)がEに含まれてない
このときは何も距離は変化しない

よって
E[Δφ(r,s)]≦-(k-d)/kn+2d/kn=(3d-k)/kn

k≧3d+1であれば0以下になるのでmixing timeは
τ(ε)≦ln(nε^{-1})/(1-1/kn)
よってThmよりMCcol は O(nln(nε^{-1}))mixingである。

しかしながら、まだなぜUを考えるとmixing timeがboundできるのかは理解できていない。couplingもしかり。

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の数を算出してみたい。