Courcelleの定理

同義語:Courcelle's theoremCourcelle theorem

概要

Courcelleの定理(Courcelle's theorem)とは、頂点や辺の集合を量化する単項二階論理 MSO₂ の文 $\varphi$ と整数 $k$ ごとに、木幅 $k$ 以下のグラフで $\varphi$ が成り立つかを頂点数に比例する時間で判定する算法があるという定理である。量化子階数を固定すると構造の型は有限通りしかなく、名前のついた頂点で構造を貼り合わせたものの型は部品の型だけで決まるので、木分解の袋を根に向かって貼り合わせながら型を表で求めればよい。3 彩色可能性や Hamilton 閉路の存在のように一般には NP完全な性質も、木幅が定数以下なら線形時間で判定できる。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 木幅, 二階論理

Courcelleの定理(Courcelle's theorem)は、グラフの性質が単項二階論理の文で書けるなら、木幅 が定数以下のグラフについて、その性質を頂点数に比例する時間で判定できる、という定理である。Courcelle が 1990 年に示した(Cou90)。
3 彩色可能性や Hamilton 閉路の存在は、一般のグラフでは NP完全 な問題である。一方で、どちらも「頂点の集合が 3 つあって…」「辺の集合があって…」のように、頂点や辺の集合を量化する文で書ける。木幅が小さいグラフでは、木分解に沿って下から表を作る 動的計画法 で多くの問題が速く解けるが、Courcelle の定理は、表に何を記録すればよいかを論理式の側から一斉に与える。鍵は、量化の深さを固定すると、部分グラフの「型」(その部分で成り立つ文の全体)が有限通りしかなく、部分を貼り合わせたものの型が部分の型だけで決まることである。
この記事では、文 $\varphi$ と幅 $k$ ごとに定数 $C(\varphi,k)$ と判定の算法があることを証明する(thm-cc-main)。証明は型の有限性(lem-cc-finite)、貼り合わせの型(lem-cc-compose)、木分解に沿った組み立て(lem-cc-tree)からなる。

内容場所
論理式と構造def-cc-structure、def-cc-mso、def-cc-mso2
主定理thm-cc-main
型の有限性lem-cc-finite
貼り合わせdef-cc-glue、lem-cc-compose、cor-cc-type
木分解に沿った組み立てlem-cc-tree
線形時間の判定cor-cc-linear
3 彩色と Hamilton 閉路ex-cc-color、ex-cc-hamilton

定義

この記事のグラフは有限の単純な無向グラフとする。$[K]:=\{1,\dots,K\}$ と書く。

名前と印のついたグラフ

木分解に沿って部分グラフを貼り合わせるため、いくつかの頂点に名前をつけたグラフを考える。正の整数 $K$ と $\ell\ge0$ を固定する。

構造

構造 $\mathfrak A=(V,E,P_1,\dots,P_\ell,\nu)$ とは、有限の単純グラフ $(V,E)$、部分集合 $P_1,\dots,P_\ell\subseteq V$(印)、ある部分集合 $N(\mathfrak A)\subseteq[K]$ から $V$ への単射 $\nu$ の組である。$\nu(i)$ を 名前 $i$ の頂点という。名前 $i\in N(\mathfrak A)$ について $\lambda_{\mathfrak A}(i):=\{j\mid\nu(i)\in P_j\}$ とおく。辺・印・名前を保つ頂点の全単射があるとき、2 つの構造は 同型 であるという。

集合変数の論理式

集合変数だけの単項二階論理

変数 $X,Y,Z,\dots$ は構造の頂点集合の部分集合を動く。原子論理式 は
$$ \top,\quad X\subseteq Y,\quad \operatorname{adj}(X,Y),\quad X\subseteq P_j\ (j\in[\ell]),\quad i\in X\ (i\in[K]) $$
であり、論理式は原子論理式から $\lnot,\land,\lor,\exists X,\forall X$ で作る。$\top$ はつねに真、$\operatorname{adj}(X,Y)$ は $x\in X$、$y\in Y$ で $xy\in E$ となるものがあるとき真、$i\in X$ は $i\in N(\mathfrak A)$ かつ $\nu(i)\in X$ のとき真とする。量化子階数 $\operatorname{qr}$ は、原子論理式で $0$、$\lnot$ で変わらず、$\land,\lor$ で大きい方、量化 1 つで $1$ 増える。自由変数のない論理式を 文 という。2 つの論理式が、すべての構造と自由変数へのすべての値の割り当てで同じ真偽をとるとき 同値 という。

次の略記を使う。$\psi\to\theta$ は $\lnot\psi\lor\theta$ のことで、
$$ \operatorname{Emp}(X):=\forall Y\,(X\subseteq Y),\qquad \operatorname{Sing}(X):=\lnot\operatorname{Emp}(X)\land\forall Y\,\bigl(Y\subseteq X\to(\operatorname{Emp}(Y)\lor X\subseteq Y)\bigr) $$
とおく。$\operatorname{Emp}(X)$ は $X=\emptyset$ のとき、$\operatorname{Sing}(X)$ は $X$ がちょうど 1 元のときに真である(2 元以上なら 1 元の部分集合 $Y$ が条件を満たさない)。1 元集合を使えば頂点を量化できるので、名前も印もない構造($\ell=0$、$N=\emptyset$)について、これはグラフの通常の単項二階論理(頂点集合だけを量化する二階論理。二階論理)と同じ表現力をもつ。
グラフの性質を書くには、辺の集合も量化できる次の論理を使う。

MSO₂

グラフ $G$ についての MSO₂ の論理式は、頂点の変数 $u,v,\dots$、辺の変数 $e,f,\dots$、頂点集合の変数、辺集合の変数の 4 種類の変数をもち、原子論理式は $u\in X$($u$ が頂点の変数で $X$ が頂点集合の変数、または $u$ が辺の変数で $X$ が辺集合の変数)、$\operatorname{inc}(u,e)$(頂点 $u$ が辺 $e$ の端点である)、$x=y$(同じ種類の変数)である。これらから $\lnot,\land,\lor$ と、4 種類の変数それぞれの $\exists,\forall$ で論理式を作る。文 $\varphi$ が $G$ で成り立つことを $G\models\varphi$ と書く。

この定義は Cyg15 §7.4.1(pp. 180–182)による。たとえば頂点 $u,v$ の隣接は $\lnot u=v\land\exists e\,(\operatorname{inc}(u,e)\land\operatorname{inc}(v,e))$ と書ける(同 p. 181)。

主定理

Courcelleの定理

$\varphi$ を MSO₂ の文、$k\ge1$ を整数とする。定数 $C=C(\varphi,k)$ と、次の算法がある:グラフ $G$(頂点 $n$ 個、辺 $m$ 個)と、$G$ の幅 $k$ 以下の木分解 $(T,(V_t)_{t\in V(T)})$ を入力として、$G\models\varphi$ かどうかを $C\,(n+m+\lvert V(T)\rvert)$ 以下の時間で判定する。

証明の組み立て

量化子階数 $q$ 以下の文で区別できるかどうかで構造を分けると、分け方は有限通りである(lem-cc-finite)。名前で頂点を同一視して構造を貼り合わせると、結果の型は部品の型だけで決まる(lem-cc-compose、cor-cc-type)。木分解の各袋を名前のついた小さな構造とみて、根に向かって貼り合わせると $G$ ができる(lem-cc-tree)。MSO₂ の文は、辺も頂点として扱う接続グラフについての集合変数の文に直せる(prop-cc-incidence)。型の表は $\varphi$ と $k$ だけで決まる有限の表なので、各ノードで定数時間の表引きをすればよい。証明は prf-cc-main にまとめる。

型の有限性

以下、$K$ と $\ell$ を固定し、構造と論理式はこの $K,\ell$ についてのものとする。

型の有限性

変数の有限集合 $\mathcal X$ と $q\ge0$ について、自由変数が $\mathcal X$ に含まれ量化子階数が $q$ 以下の論理式は、同値なものを同一視すると有限個しかない。

$q$ についての帰納法による。量化子階数が $q$ 以下の論理式は、原子論理式と、$\exists Y\psi$ または $\forall Y\psi$($\operatorname{qr}\psi\le q-1$)の形の論理式から $\lnot,\land,\lor$ で作られるので、それらのうち有限個の真偽の関数として表せることを示せばよい。

帰納法の詳細を開く

$q=0$ のとき:自由変数が $\mathcal X$ に含まれる原子論理式は有限個($a$ 個とする)で、論理式の真偽はそれらの真偽で決まる。真偽の組から真偽への関数は $2^{2^a}$ 個なので、同値類は $2^{2^a}$ 個以下である。

$q\ge1$ のとき:$\mathcal X$ に入らない変数 $Y_*$ を 1 つ固定する。束縛変数の名前を付け替えて、$\exists Y\psi$ は $\exists Y_*\psi'$($\psi'$ の自由変数は $\mathcal X\cup\{Y_*\}$ に含まれ、$\operatorname{qr}\psi'\le q-1$)と同値である。$\psi'$ を同値なものに取り替えても $\exists Y_*\psi'$ の真偽は変わらないので、帰納法の仮定により $\exists Y_*\psi'$ の形の論理式の同値類は有限個である。$\forall Y_*\psi'$ は $\lnot\exists Y_*\lnot\psi'$ と同値である。よって、原子論理式とこれらの有限個の代表、合わせて $b$ 個の真偽で論理式の真偽が決まり、同値類は $2^{2^b}$ 個以下である。$\square$

一階の論理式についての同じ有限性は Ehrenfeucht–Fraïsséゲーム でも使われる。

型

構造 $\mathfrak A$ の $q$ 型 $\operatorname{tp}_q(\mathfrak A)$ を、$N(\mathfrak A)$、$\lambda_{\mathfrak A}$、および $\mathfrak A$ で真になる量化子階数 $q$ 以下の文の同値類の集合、の 3 つ組とする。

lem-cc-finite($\mathcal X=\emptyset$)により、$q$ 型は有限通りしかない。同型な構造は同じ $q$ 型をもつ。

貼り合わせ

貼り合わせ

構造 $\mathfrak A,\mathfrak B$ が 両立する とは、共通の名前 $i\in N(\mathfrak A)\cap N(\mathfrak B)$ について $\lambda_{\mathfrak A}(i)=\lambda_{\mathfrak B}(i)$ であることをいう。両立する $\mathfrak A,\mathfrak B$ の 貼り合わせ $\mathfrak A\oplus\mathfrak B$ は、$\mathfrak A$ と $\mathfrak B$ の非交和で、共通の名前 $i$ ごとに名前 $i$ の 2 頂点を 1 つにしたものである。辺・印は両方の像の和、名前の集合は $N(\mathfrak A)\cup N(\mathfrak B)$ とする。自然な写像を $\iota_{\mathfrak A}\colon V(\mathfrak A)\to V(\mathfrak A\oplus\mathfrak B)$、$\iota_{\mathfrak B}$ と書く。名前の集合 $M\subseteq[K]$ について、$M$ に入る名前を消した構造を $\mathfrak A\setminus M$ と書く。

$Z\subseteq V(\mathfrak A\oplus\mathfrak B)$ に $(\iota_{\mathfrak A}^{-1}(Z),\iota_{\mathfrak B}^{-1}(Z))$ を対応させると、$Z$ と、次の条件をみたす組 $(Z_{\mathfrak A},Z_{\mathfrak B})$ が 1 対 1 に対応する:共通の名前 $i$ について「$\nu_{\mathfrak A}(i)\in Z_{\mathfrak A}$ と $\nu_{\mathfrak B}(i)\in Z_{\mathfrak B}$ が同値」。この条件をみたす組を 境界で一致する 組という。

対応の確かめを開く

境界で一致する組から $Z:=\iota_{\mathfrak A}(Z_{\mathfrak A})\cup\iota_{\mathfrak B}(Z_{\mathfrak B})$ を作ると、$\iota_{\mathfrak A}^{-1}(Z)$ に $Z_{\mathfrak A}$ の外から加わりうるのは共通の名前の頂点だけで、条件によりそれは $Z_{\mathfrak A}$ にすでに入っている。$\mathfrak B$ の側も同じである。

貼り合わせの分解

$N_1,N_2\subseteq[K]$ を固定する。論理式 $\varphi(X_1,\dots,X_p)$ ごとに、自由変数が $X_1,\dots,X_p$ に含まれ量化子階数が $\operatorname{qr}\varphi$ 以下の論理式の組 $(\alpha_j,\beta_j)$($j\in J$、$J$ は有限)があって、次が成り立つ:$N(\mathfrak A)=N_1$、$N(\mathfrak B)=N_2$ である両立する構造 $\mathfrak A,\mathfrak B$ と、$Z_1,\dots,Z_p\subseteq V(\mathfrak A\oplus\mathfrak B)$ について
$$ \mathfrak A\oplus\mathfrak B\models\varphi(\bar Z)\iff\text{ある }j\in J\text{ で }\mathfrak A\models\alpha_j(\iota_{\mathfrak A}^{-1}\bar Z)\text{ かつ }\mathfrak B\models\beta_j(\iota_{\mathfrak B}^{-1}\bar Z). $$
ここで $\iota_{\mathfrak A}^{-1}\bar Z:=(\iota_{\mathfrak A}^{-1}(Z_1),\dots,\iota_{\mathfrak A}^{-1}(Z_p))$ である。

$\varphi$ の作り方についての帰納法による。$A_i:=\iota_{\mathfrak A}^{-1}(Z_i)$、$B_i:=\iota_{\mathfrak B}^{-1}(Z_i)$ とおく。$Z_i=\iota_{\mathfrak A}(A_i)\cup\iota_{\mathfrak B}(B_i)$ である。原子論理式では、$\mathfrak A\oplus\mathfrak B$ の辺・印・名前が両側の像の和であることから組が直接書け、$\land,\lor,\lnot$ では組を組み合わせればよい。

原子論理式と $\land,\lor,\lnot$ の場合を開く

原子論理式:$\top$ には $(\top,\top)$ をとる。$Z_1\subseteq Z_2$ は $A_1\subseteq A_2$ かつ $B_1\subseteq B_2$ と同値なので $(X_1\subseteq X_2,\ X_1\subseteq X_2)$ をとる。$\mathfrak A\oplus\mathfrak B$ の辺は $\mathfrak A$ か $\mathfrak B$ の辺の像なので、$\operatorname{adj}(Z_1,Z_2)$ は $\mathfrak A\models\operatorname{adj}(A_1,A_2)$ または $\mathfrak B\models\operatorname{adj}(B_1,B_2)$ と同値で、$(\operatorname{adj},\top)$ と $(\top,\operatorname{adj})$ をとる。$Z_1\subseteq P_j$ は $A_1\subseteq P_j^{\mathfrak A}$ かつ $B_1\subseteq P_j^{\mathfrak B}$ と同値である:$\iota_{\mathfrak A}(a)$ が $\mathfrak B$ の側から $P_j$ に入るのは $a$ が共通の名前の頂点のときだけで、両立性から $a\in P_j^{\mathfrak A}$ だからである。$i\in X_1$ は、$i\in N_1$ なら $(i\in X_1,\top)$、$i\in N_2\setminus N_1$ なら $(\top,i\in X_1)$ をとり、$i\notin N_1\cup N_2$ なら組を 1 つもとらない(偽)。

$\land,\lor$:$\varphi$ の組 $(\alpha_j,\beta_j)_{j\in J}$、$\psi$ の組 $(\gamma_h,\delta_h)_{h\in H}$ について、$\varphi\land\psi$ には $(\alpha_j\land\gamma_h,\ \beta_j\land\delta_h)$、$\varphi\lor\psi$ には 2 つの組の族の和をとる。

$\lnot$:$\varphi$ の組を $(\alpha_j,\beta_j)_{j\in J}$ とする。$S\subseteq J$ について $\hat\alpha_S:=\bigwedge_{j\in S}\alpha_j\land\bigwedge_{j\notin S}\lnot\alpha_j$ とおき、$\hat\beta_S$ も同様に定める。値の割り当てごとに $\mathfrak A$ で真な $\hat\alpha_S$ と $\mathfrak B$ で真な $\hat\beta_{S'}$ がただ 1 つずつあり、$\varphi$ が真であることは $S\cap S'\ne\emptyset$ と同値である。よって $\lnot\varphi$ には $S\cap S'=\emptyset$ となる組 $(\hat\alpha_S,\hat\beta_{S'})$ の全体をとる。


$\exists$ の場合.$\varphi=\exists Y\psi(\bar X,Y)$($Y$ は $X_i$ と異なるとしてよい)とし、$\psi$ の組を $(\alpha_j,\beta_j)_{j\in J}$ とする。$\mathit{Sh}:=N_1\cap N_2$ と $Q\subseteq\mathit{Sh}$ について $\theta_Q(Y):=\bigwedge_{i\in Q}(i\in Y)\land\bigwedge_{i\in\mathit{Sh}\setminus Q}\lnot(i\in Y)$ とおき、$\varphi$ には
$$ \bigl(\exists Y(\alpha_j\land\theta_Q),\ \exists Y(\beta_j\land\theta_Q)\bigr)\qquad(j\in J,\ Q\subseteq\mathit{Sh}) $$
をとる。量化子階数は $\operatorname{qr}\psi+1$ 以下である。$\mathfrak A\oplus\mathfrak B\models\varphi(\bar Z)$ なら、$\psi(\bar Z,W)$ が真な $W$ があり、帰納法の仮定からある $j$ で $\mathfrak A\models\alpha_j(\bar A,\iota_{\mathfrak A}^{-1}W)$、$\mathfrak B\models\beta_j(\bar B,\iota_{\mathfrak B}^{-1}W)$ である。$Q:=\{i\in\mathit{Sh}\mid\nu(i)\in W\}$ とすれば両側で $\theta_Q$ も真である。逆に、ある $j,Q$ で両側の論理式が真なら、それを実現する $W_{\mathfrak A},W_{\mathfrak B}$ はどちらも共通の名前のうち $Q$ に入るものの頂点だけを含むので境界で一致し、ある $W$ について $W_{\mathfrak A}=\iota_{\mathfrak A}^{-1}(W)$、$W_{\mathfrak B}=\iota_{\mathfrak B}^{-1}(W)$ である。帰納法の仮定から $\psi(\bar Z,W)$ は真である。$\forall Y$ は $\lnot\exists Y\lnot$ に直す。$\square$

この分解は、部分の真偽から全体の真偽を組み立てる議論で、直積についての Feferman–Vaughtの定理 と同じ型である。

型の合成

$q\ge0$ とする。

  1. 両立する構造 $\mathfrak A,\mathfrak B$ について、$\operatorname{tp}_q(\mathfrak A\oplus\mathfrak B)$ は $\operatorname{tp}_q(\mathfrak A)$ と $\operatorname{tp}_q(\mathfrak B)$ だけで決まる。
  2. $M\subseteq[K]$ について、$\operatorname{tp}_q(\mathfrak A\setminus M)$ は $\operatorname{tp}_q(\mathfrak A)$ と $M$ だけで決まる。

1:名前の集合は $N(\mathfrak A)\cup N(\mathfrak B)$ で、$\lambda$ は両側の $\lambda$ を合わせたものである。量化子階数 $q$ 以下の文 $\sigma$ に lem-cc-compose($N_1=N(\mathfrak A)$、$N_2=N(\mathfrak B)$、$p=0$)を使うと、$\sigma$ の真偽は、量化子階数 $q$ 以下の文 $\alpha_j,\beta_j$ の $\mathfrak A,\mathfrak B$ での真偽で決まり、それらは型に記録されている。
2:文 $\sigma$ の原子論理式 $i\in X$($i\in M$)を $\lnot\top$ に置き換えた文を $\sigma^M$ とすると、量化子階数は変わらず、$\mathfrak A\setminus M\models\sigma$ と $\mathfrak A\models\sigma^M$ は同値である(ほかの原子論理式の意味は変わらない)。名前の集合は $N(\mathfrak A)\setminus M$ で、$\lambda$ はその制限である。$\square$

木分解に沿った組み立て

$G$ を印 $P_1,\dots,P_\ell$ のついたグラフ、$(T,(V_t))$ を幅 $k$ 以下の木分解とし、$K:=k+1$ とする。$T$ に根 $r$ を定め、ノード $t$ の子孫($t$ を含む)のなす部分木を $T_t$、$U_t:=\bigcup_{s\in T_t}V_s$ とおく。頂点 $v$ を含む袋のノードの集合 $T(v)$ は (T3) により部分木である(木幅 の定義「木分解と木幅」)。

木分解に沿った組み立て
  1. 各頂点 $v$ について、$T(v)$ のうち根に最も近いノード $\operatorname{top}(v)$ はただ 1 つで、各袋の上で単射な $\chi\colon V(G)\to[K]$ がある。
  2. 辺 $uv$ について、$\operatorname{top}(u),\operatorname{top}(v)$ のうち根から遠い方 $t(uv)$ の袋は $u,v$ を含む。
  3. 辺 $uv$ をノード $t(uv)$ に割り当て、$\mathfrak B_t$ を、頂点集合 $V_t$、$t$ に割り当てた辺、印の制限、名前 $\chi(v)$ の頂点を $v$ とする名前からなる構造とする。$t$ の子を $c_1,\dots,c_d$、$M_c:=\chi(V_c\setminus V_t)$ として、葉から順に
    $$ \mathfrak G_t:=\bigl(\cdots\bigl(\mathfrak B_t\oplus(\mathfrak G_{c_1}\setminus M_{c_1})\bigr)\oplus\cdots\bigr)\oplus(\mathfrak G_{c_d}\setminus M_{c_d}) $$
    とおく。$\mathfrak G_t$ は、頂点集合 $U_t$、$T_t$ のノードに割り当てた辺、印の制限、名前 $\chi|_{V_t}$ からなる構造 $\mathfrak H_t$ と同型である。とくに $\mathfrak G_r\setminus[K]$ は $G$(名前なし)と同型である。

1 と 2 は (T3) から従う:$\chi$ は根から順に、まだ色のない頂点に袋の中で使われていない色を与えて作り、辺 $uv$ を含む袋のノードの祖先のうちで $\operatorname{top}(u)$ と $\operatorname{top}(v)$ が比べられることを使う。

1 と 2 の証明を開く

1:$T(v)$ の根に最も近いノードが 2 つあれば、それらを結ぶ道は根により近いノードを通り、そのノードも部分木 $T(v)$ に入って矛盾する。$\chi$ は根から順に決める。ノード $t$ で、$\operatorname{top}(v)\ne t$ である $v\in V_t$ について、$\operatorname{top}(v)$ は $t$ の真の祖先なので、$t$ と $\operatorname{top}(v)$ を結ぶ道は $t$ の親 $p$ を通り、(T3) により $v\in V_p$ である。これらの頂点は $V_p$ の上で単射に色がついている。$\operatorname{top}(v)=t$ である頂点に、残りの色から相異なるものを与える。$\lvert V_t\rvert\le K$ なので足りる。(T1) によりどの頂点もちょうど 1 度色を受ける。

2:$\operatorname{top}(u)$ が根から遠い方(同じ深さを含む)とする。(T2) により $u,v\in V_s$ となる $s$ がある。$\operatorname{top}(u)$、$\operatorname{top}(v)$ はどちらも $s$ の祖先($s$ 自身を含む)なので一方が他方の祖先であり、$\operatorname{top}(v)$ は $\operatorname{top}(u)$ の祖先である。$\operatorname{top}(u)$ は $\operatorname{top}(v)$ と $s$ を結ぶ道の上にあり、(T3) により $v\in V_{\operatorname{top}(u)}$ である。


3:子 $c$ について次の 2 つが成り立つ。(a) $U_c\cap V_t=V_c\cap V_t$:$v\in V_s\cap V_t$($s\in T_c$)なら $s$ と $t$ を結ぶ道は $c$ を通る。(b) 子 $c\ne c'$ について $U_c\cap U_{c'}\subseteq V_t$:$T_c$ と $T_{c'}$ のノードを結ぶ道は $t$ を通る。どちらも (T3) による。
葉から帰納法で示す。帰納法の仮定から $\mathfrak G_c\cong\mathfrak H_c$ で、名前は $\chi|_{V_c}$ なので、$\mathfrak G_c\setminus M_c$ は名前 $\chi|_{V_c\cap V_t}$ をもつ $\mathfrak H_c$ と同型である。$\chi$ は $V_t$ の上で単射なので、貼り合わせで名前 $\chi(v)$ の頂点どうしが 1 つになることは、同じ頂点 $v\in V_c\cap V_t$ の写しが $V_t$ の $v$ と 1 つになることである。(a) により $U_c$ のうち $V_t$ に入る頂点にはすべて名前があり、名前のない $U_c\setminus V_t$ の頂点は、(b) によりほかの子の部分とも $V_t$ とも重ならない。よって頂点集合は $V_t\cup\bigcup_cU_c=U_t$ に 1 対 1 に対応し、辺は $t$ と各 $T_c$ に割り当てた辺の和、印は $G$ の印の制限である。共通の名前は同じ頂点を指すので、各段の貼り合わせは両立している。根では (T1) から $U_r=V(G)$ で、2 によりすべての辺がどこかに割り当てられている。$\square$

接続グラフへの書き換え

グラフ $G$ の 接続グラフ $I(G)$ を、頂点集合 $V(G)\sqcup E(G)$、辺 $\{u,e\}$($u$ が $e$ の端点)をもち、印 $P_1:=V(G)$ をもつグラフとする。

接続グラフへの書き換え
  1. MSO₂ の文 $\varphi$ ごとに、$\ell=1$ の集合変数の文 $\varphi^*$ があり、すべてのグラフ $G$ について $G\models\varphi$ と $I(G)\models\varphi^*$ は同値である。
  2. $G$ の幅 $k$ 以下の木分解から、$I(G)$ の幅 $\max(k,2)$ 以下でノードが $m$ 個多い木分解が $O(\sum_t\lvert V_t\rvert+m)$ 時間で得られる。

1:頂点や辺の変数は $\operatorname{Sing}$ をみたす集合変数に、$\operatorname{inc}$ は $\operatorname{adj}$ に置き換え、印 $P_1$ で頂点と辺を区別する。

置き換えの詳細を開く

変数ごとに集合変数 $Z$ を対応させ、量化を $\exists v\mapsto\exists Z(\operatorname{Sing}(Z)\land Z\subseteq P_1\land\cdots)$、$\exists e\mapsto\exists Z(\operatorname{Sing}(Z)\land D(Z)\land\cdots)$、頂点集合 $\exists X\mapsto\exists Z(Z\subseteq P_1\land\cdots)$、辺集合 $\exists F\mapsto\exists Z(D(Z)\land\cdots)$ と置き換える。ここで $D(Z):=\forall W\bigl((W\subseteq Z\land W\subseteq P_1)\to\operatorname{Emp}(W)\bigr)$ は $Z\cap P_1=\emptyset$ を表す。原子論理式は $u\in X\mapsto Z_u\subseteq Z_X$、$\operatorname{inc}(u,e)\mapsto\operatorname{adj}(Z_u,Z_e)$、$x=y\mapsto Z_x\subseteq Z_y\land Z_y\subseteq Z_x$ と置き換える。各変数の値と、それに対応する 1 元集合や集合が 1 対 1 に対応し、原子論理式の真偽が一致するので、論理式の作り方についての帰納法で同値性が従う。


2:lem-cc-tree の 2 で各辺 $e=uv$ に $u,v$ を含む袋のノード $t(e)$ を選び、袋 $\{u,v,e\}$ をもつ葉を $t(e)$ につなぐ。(T1)(T2) は明らかで、$e$ はその葉の袋だけに入り、頂点 $u$ を含むノードの集合は $T(u)$ にそれにつながる葉を加えたものなので部分木である。袋の大きさは $\max(k+1,3)$ 以下である。$\square$

主定理の証明

$k':=\max(k,2)$、$K:=k'+1$、$\ell:=1$ とし、prop-cc-incidence の文 $\varphi^*$ の量化子階数を $q$ とする。lem-cc-finite により $q$ 型は有限通りで、cor-cc-type により、次の 3 つは有限の表で与えられる。(i) 2 つの $q$ 型から貼り合わせの $q$ 型を返す表。(ii) $q$ 型と $M\subseteq[K]$ から名前を消した構造の $q$ 型を返す表。(iii) $K$ 個以下の頂点がすべて名前をもつ構造の $q$ 型の表(そのような構造は同型を除いて有限個である)。さらに (iv) $\varphi^*$ の同値類が型の第 3 成分に入るかどうかの表。これらは $\varphi$ と $k$ だけで決まり、算法に書き込んでおく。
算法:$I(G)$ とその幅 $k'$ 以下の木分解を作る(prop-cc-incidence の 2)。根を定め、深さ、$\operatorname{top}$、$\chi$、辺の割り当てを求める(lem-cc-tree の 1、2)。葉から順に、表 (iii) で $\operatorname{tp}_q(\mathfrak B_t)$ を求め、各子 $c$ について表 (ii) と (i) で $\operatorname{tp}_q(\mathfrak G_t)$ を更新する。最後に表 (ii) で $\operatorname{tp}_q(\mathfrak G_r\setminus[K])$ を求め、表 (iv) で答える。
正しさ:lem-cc-tree の 3 により $\mathfrak G_r\setminus[K]\cong I(G)$ で、同型な構造の型は等しいので $\operatorname{tp}_q(I(G))$ が得られ、prop-cc-incidence の 1 により $I(G)\models\varphi^*$ と $G\models\varphi$ は同値である。
時間:$I(G)$ の頂点は $n+m$ 個、辺は $2m$ 本、木分解のノードは $\lvert V(T)\rvert+m$ 個で、袋の大きさは $K$ 以下である。$\operatorname{top}$ と $\chi$ は袋を根から 1 度ずつ見て、辺の割り当ては辺ごとに定数回の比較で求まる。各ノードでは $\mathfrak B_t$ を作る($K^2$ 以下と割り当てた辺の数に比例する手間)、表 (iii) を 1 度、子ごとに表 (i)(ii) を 1 度ずつ引く。合計は $n+m+\lvert V(T)\rvert$ の定数倍で、定数は $\varphi$ と $k$ だけで決まる。$\square$

定数の計算可能性

上の証明は、表 (i)〜(iv) が存在することを示すが、それを $\varphi$ と $k$ から求める手順は与えていない。Cyg15 Theorem 7.11(p. 183)は、MSO₂ の論理式 $\varphi$(自由変数の値も入力に含める)と幅 $t$ の木分解について、$\varphi$ の長さを $L$ として、計算可能な関数 $f$ による $f(L,t)\cdot n$ 時間の算法として定理を述べている。この記事では計算可能性は扱わない。

系

木幅が小さいグラフでの線形時間の判定

$\varphi$ を MSO₂ の文、$k\ge1$ とする。木幅 $k$ 以下のグラフ $G$ について $G\models\varphi$ かどうかを、頂点数 $n$ の定数倍の時間で判定する算法がある。

Cyg15 Theorem 7.17(p. 191)により、$k^{O(k^3)}\cdot n$ 時間で、幅 $k$ 以下の木分解を作るか木幅が $k$ より大きいと判定する算法がある。出力の大きさは時間を超えないので、ノードの数も $n$ の定数倍である。木幅 $k$ 以下のグラフのどの部分グラフも木幅 $k$ 以下で、最小次数は $k$ 以下である(木幅 の命題「最小次数による評価」)。次数 $k$ 以下の頂点を除くことを繰り返すと、辺は 1 回に $k$ 本以下ずつ減るので $m\le kn$ である。thm-cc-main と合わせて結論を得る。$\square$

例

3 彩色可能性

グラフの グラフ彩色 で 3 色が足りることは、頂点集合 $X_1,X_2,X_3$ があって、どの頂点もどれかに入り、どの $X_i$ の 2 頂点も隣接しないことであり、MSO₂ の文で書ける。cor-cc-linear により、木幅 $k$ 以下のグラフの 3 彩色可能性は線形時間で判定できる。

文を開く

$\exists X_1\exists X_2\exists X_3\bigl(\forall v\,(v\in X_1\lor v\in X_2\lor v\in X_3)\land\forall u\forall v\,(\operatorname{adj}(u,v)\to\bigwedge_{i}\lnot(u\in X_i\land v\in X_i))\bigr)$。ここで $\operatorname{adj}(u,v)$ は def-cc-mso2 のあとの略記である。Cyg15 p. 182 は、$X_1,X_2,X_3$ が頂点集合の分割であることを要求する同じ形の文を挙げている。

Hamilton 閉路の存在

3 頂点以上のグラフが Hamilton閉路 をもつことは、辺の集合 $F$ で、$(V,F)$ が連結で、どの頂点にも $F$ の辺がちょうど 2 本接続するものがあることと同値である。これは辺の集合を量化する MSO₂ の文で書ける(Cyg15 p. 182)。

同値性と文を開く

そのような $F$ では、どの頂点の次数も 2 の連結グラフ $(V,F)$ は 1 つの閉路で、全頂点を通る。逆は Hamilton 閉路の辺の集合をとればよい。連結性は「$V$ を空でない 2 つに分けると、間をつなぐ $F$ の辺がある」と書く:$\forall Y\bigl((\exists u\,u\in Y\land\exists v\,\lnot v\in Y)\to\exists e\,\exists u\,\exists v\,(e\in F\land u\in Y\land\lnot v\in Y\land\operatorname{inc}(u,e)\land\operatorname{inc}(v,e))\bigr)$。次数 2 は、異なる 2 辺 $e_1,e_2\in F$ が $v$ に接続し、$v$ に接続する $F$ の辺はそのどちらかである、と書く。

反例

外した仮定反例成り立たなくなる結論
名前で頂点を同一視する(cor-cc-type の 1)辺 $pq$ と $p$ につないだ葉からなるグラフ 2 つを、$p$ どうし・$q$ どうしで 1 つにする場合と、$p$ と $q$ を入れ替えて 1 つにする場合貼り合わせた構造の $6$ 型が部品の $6$ 型だけで決まる
(T3)(lem-cc-tree の 3)辺のない 2 頂点 $x,y$ のグラフと、道 $t_1t_2t_3$ に袋 $\{x\},\{y\},\{x\}$ を並べ、根を $t_2$、$\chi(x)=1$、$\chi(y)=2$ としたもの$\mathfrak G_r\setminus[K]$ が $G$ と同型
木幅が $k$ 以下(cor-cc-linear)すべてのグラフについての 3 彩色可能性(ex-cc-color)多項式時間で判定できる(P $\ne$ NP のとき)
反例の確かめ

どの行も、右の欄の主張が成り立たないことを直接確かめられる。

確かめを開く

1 行目:2 つの部品は同じグラフで、同じ境界 $\{p,q\}$ をもつ。$p$ どうしを 1 つにすると $p$ は $q$ と 2 枚の葉に隣接して次数 3 になる。入れ替えると、片方の $p$ と他方の $q$ が 1 つになり、結果は 4 頂点の道で次数はすべて 2 以下である。「次数 3 以上の頂点がある」は $\exists X\exists Y_1\exists Y_2\exists Y_3\bigl(\operatorname{Sing}(X)\land\bigwedge_i\operatorname{Sing}(Y_i)\land\bigwedge_{i\ne j}\lnot Y_i\subseteq Y_j\land\bigwedge_i\operatorname{adj}(X,Y_i)\bigr)$ と書け、$\operatorname{Sing}$ の量化子階数は 2 なので量化子階数 6 の文である。よって、同じ部品から型の違う構造ができる。名前による貼り合わせでは、入れ替えは部品の名前を付け替えることにあたり、部品の型が変わる。

2 行目:袋は (T1)(T2) をみたすが、$x$ を含む $t_1,t_3$ の間の $t_2$ が $x$ を含まないので (T3) が満たされない。$\chi$ は各袋で単射である。$M_{t_1}=M_{t_3}=\chi(\{x\})=\{1\}$ なので、$\mathfrak G_{t_1}\setminus M_{t_1}$ と $\mathfrak G_{t_3}\setminus M_{t_3}$ はどちらも名前のない 1 頂点で、$\mathfrak G_{t_2}$ は $y$ と 2 つの名前のない頂点の 3 頂点になる。$G$ は 2 頂点である。

3 行目:3 彩色可能性は NP完全である(NP完全 の定理「3 彩色可能性の NP完全性」)。P $\ne$ NP なら、NP完全な問題を多項式時間で解く算法はない。

関連項目

参考文献

[1]
Bruno Courcelle, The monadic second-order logic of graphs. I. Recognizable sets of finite graphs, Information and Computation, 1990, 12–75

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する