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もしかり。