木幅と線形時間アルゴリズム

今回は木幅（tree-width）の話を書いてみようと思います。

木幅とは、大雑把に言うとグラフがどれだけ木に近いかを表す値です（木に近いほど小さな値になります）。NP困難な問題でもグラフを木に限定すると多項式時間で解けたりする話は有名ですが、実は一部のNP困難な問題は、グラフの木幅が定数で上から抑えられるなら、なんと線形時間で解くことができます！

今回はそのようなNP困難問題の一つである最大独立集合問題を取り上げて、木幅が定数で抑えられるときの線形時間アルゴリズムを紹介することを目標に記事を書いていこうと思います。

1. 木分解と木幅

 木幅を定義する前に、まずは木分解（tree-decomposition）を定義します。木分解とは、グラフを木構造として表現したものです。ちなみにグラフは無向グラフのみを考えます。

定義（木分解）

 グラフ$G=(V,E)$に対して、頂点集合$V$の部分集合族$X=\{X_1, X_2, ..., X_k\}$と$X_1, X_2, ..., X_k$を節点として持つ木$T$の組$(X,T)$であって、以下を満たすものを$G$の木分解という。

1. $X_i(i=1, 2, ..., k)$の和集合は$V$
2. $G$において辺で結ばれている任意の2点$(u,v)$に対して、$u$、$v$を両方とも含む$X_i$が存在する
3. $G$の任意の頂点$v\in V$に対して、$v$を含む$X_i$全体は$T$上で連結

 イメージとしては、$G$の各頂点$v$に、$v$を含む$X_i$全体がなす$T$の部分木が対応しています。$G$で頂点$u$と$v$の間に辺があるなら、$u$に対応する$T$の部分木と$v$に対応する$T$の部分木が交わりを持つ（つまり$u$、$v$を両方含む$T$の節点$X_i$が存在する）という構造になっています。

例を見てみます。

左が元のグラフ、右が左のグラフの木分解です。先ほどの木分解の定義の1~3を満たしていることが確認できます。

木分解が定義できたので、今度は木分解の幅と、グラフの木幅を定義します。

定義（幅、木幅）

 グラフ$G$のある木分解$(X,T)$の幅とは、$\max_{X_i\in X}|X_i|-1$のことである*1。また、グラフ$G$の木幅tw$(G)$とは、$G$の全ての木分解の幅のうちの最小値である。

例えば、上の例における木分解の幅は2です。また、上の例におけるグラフは実は木幅も2です（つまり上に描いた木分解は幅が最小の木分解です）。

一般のグラフの木幅をすぐに求めるのは難しいですが、グラフクラスを限定すると木幅がすぐにわかったりします。例えば木の木幅は1であり（逆に連結なグラフで木幅が1なら木です）、また外平面的グラフ*2の木幅は2以下です。これを聞くと、確かに木幅が小さいほど木に近いグラフであるような気分になりますね*3。

さて、実は与えられたグラフの幅最小の木分解を求めるのはNP困難問題です。ですが、木幅が定数で上から抑えられるなら、以下のBodlaenderの定理を用いて（$|V|$に関する）線形時間で幅最小の木分解を求めることができます。

定理（Bodlaender 1996）

各定数$t$に対して、以下を（$t$を定数と見たときに）$O(|V|)$時間で行える。

入力として与えられたグラフ$G=(V,E)$に対して、その木幅が$t$以下であるか否かを判定し、もし$t$以下なら幅$t$以下の木分解を構成する。

 与えられたグラフ$G$の木幅が定数$l$で上から抑えられるとします。このとき、Bodlaenderの定理を$t=1,2,...,l$について順番に$G$に適用するか二部探索すれば、幅最小の木分解を（$l$を定数とみると）合計$O(|V|)$時間で得ることができます。これで幅最小の木分解を求める線形時間アルゴリズムが得られました。

（木幅が定数で抑えられるグラフに対する）最大独立集合問題の線形時間アルゴリズムも、この幅最小の木分解を求める線形時間アルゴリズムを使っています。このことは次の章以降で紹介していきます。

 2. Nice Tree-decomposition

 さて、グラフの幅最小の木分解が得られたとします。この木分解上でDPをまわすことで最大独立集合が求められるのですが、そのままDPをすると割と面倒です。そこでnice tree-decomposition と呼ばれるDPがしやすい木分解にあらかじめ変形しておいて、その木分解上でDPをまわす、ということがよく行われます*4。というわけで、この章では木分解上のDPを紹介する前にnice tree-decompositionを紹介しようと思います。

nice tree-decompositionとは、DPがしやすいように単純な構造しか持たないようにした木分解です。

定義（Nice Tree-decomposition）

nice tree-decompositionとは、木分解$(X,T)$で、$T$をある節点を根とした根付き木とみたときに以下を満たすもの*5。

1. 全ての$X_i\in X$は高々2つの子しか持たない
2. $X_i$が2つの子$X_j$、$X_k$を持つなら、$X_i=X_j=X_k$が成り立つ
3. $X_i$が1つの子$X_j$を持つなら、$G$のある頂点$v\in V$が存在して$X_i=X_j\cup \{v\}$または$X_i=X_j\setminus \{v\}$が成り立つ

2.を満たす$X_i$のことをjoin、3.を満たす$X_i$のうち$X_i=X_j\cup \{v\}$を満たすものをintroduce、$X_i=X_j\setminus \{v\}$を満たすものをforgetと呼びます。 

例えば、木分解の定義の後で例に挙げたグラフのnice tree-decompositionは以下のようになります（一意ではありません）。

 さて、（木幅が定数で抑えられるグラフに対して）幅最小の木分解が$O(|V|)$時間で得られることは前の章で説明しましたが、実はある木分解$(X,T)$から同じ幅のnice tree-decompositionを得ることも（幅を定数として）$O(|X|)$時間で可能です。

補題

グラフ$G$の木分解$(X,T)$に対して、同じ幅のnice tree-decompositionを（幅を定数として）$O(|X|)$時間で得ることができる。

証明)

与えられた木分解を$(X,T)$とする。まず、$T$の適当な節点$X_r\in X$を根と定めて、$T$を根付き木として見る。次に、以下の3ステップの操作により$T$を変形することで、同じ幅のnice tree-decompositionを構成する。

1.  3つ以上子を持つ節点の子を2つに減らす
2. 節点$X_i$が2つの子$X_j$、$X_k$を持ち、$X_i=X_j=X_k$が成り立たない場合、$X_i$の子を変える
3. 節点$X_i$が1つの子$X_j$を持ち、「$G$のある頂点$v\in V$が存在して$X_i=X_j\cup \{v\}$または$X_i=X_j\setminus \{v\}$が成り立つ」という関係が成り立たないとき、$X_i$と$X_j$の間に節点を追加する

 各ステップの操作を詳しく見ていく。

まず、ステップ1.について、ある節点$X_i$が3つ以上子を持っていたとする。$X_i$の親を$X_j$とする。このとき、$X_i$のコピーを新たにつくり、$X_j$と$X_i$の間に挿入する。また、$X_i$の子のうち、適当に1つ選んで親を$X_i$のコピーに変更する（下図参照）。

 

この変形は木分解の条件を保ち、また木分解の幅も変化しない。また、コピーのほうの$X_i$の子は2つであり、コピーでないほうの$X_i$の子はもともとの個数よりも1つ少なくなっている。つまり、$X_i$に対してこれと同じ変形をまた施し、これを（子が3つ以上の）すべての節点について帰納的に繰り返せば、有限回の変形によってすべての節点の子を2つ以下にすることができる。これによって増える節点の個数は$T$の辺の数以下なので、ステップ1.が終わった後の節点数は$O(|X|)$のままである。またステップ1.全体にかかる時間計算量は、幅を定数とみれば$O(|X|)$時間である。ステップ1.が完了すると、nice tree-decompositionの定義の1つ目の条件が満たされていることになる。

次にステップ2.について、節点$X_i$が2つの子$X_j$、$X_k$を持ち、$X_i=X_j=X_k$が成り立たないとする。このとき、新たに$X_i$のコピーを2つ作り、$X_i$と$X_j$、$X_i$と$X_k$の間にそれぞれ挿入する（下図参照）。

 この変形は木分解の条件を保ち、また木分解の幅も変化しない。この変形をステップ2.の条件に当てはまるすべての節点に対して行えば、nice tree-decompositionの定義の2つ目の条件が満たされることになる。ステップ2.全体で増える節点数、かかる時間計算量は幅を定数とみればともに$O(|X|)$である。

次にステップ3.について、節点$X_i$が1つの子$X_j$を持ち、「$G$のある頂点$v\in V$が存在して$X_i=X_j\cup \{v\}$または$X_i=X_j\setminus \{v\}$が成り立つ」という関係が成り立たないとする。$X_i\setminus X_j=\{u_1,u_2,...,u_p\}$とする。このとき、まず$X_i$と$X_j$の間に$X_i\setminus \{u_1\}$を挿入する。次に$X_i\setminus \{u_1\}$と$X_j$の間に$X_i\setminus \{u_1,u_2\}$を挿入する。次に$X_i\setminus \{u_1,u_2\}$と$X_j$の間に$X_i\setminus \{u_1,u_2,u_3\}$を挿入する...と繰り返し、最終的に$X_i\setminus\{u_1,u_2,...,u_{p-1}\}$と$X_j$の間に$X_i \setminus \{u_1,u_2,...,u_p\}$を挿入する。ちなみに$X_i \setminus \{u_1,u_2,...,u_p\}=X_i\cap X_j$である。

$X_j\setminus X_i=\{v_1,v_2,...,v_q\}$についても同様の操作を行う。つまり、まず$X_i\cap X_j$と$X_j$の間に$X_j\setminus \{v_1\}$を挿入する。次に$X_i\cap X_j$と$X_j\setminus \{v_1\}$の間に$X_j\setminus \{v_1,v_2\}$を挿入する...と繰り返し、最終的に$X_i\cap X_j$と$X_j\setminus \{v_1,v_2,...,v_{q-2}\}$の間に$X_j\setminus \{v_1,v_2,...,v_{q-1}\}$を挿入する（$X_j\setminus \{v_1,v_2,...,v_q\}=X_i\cap X_j$に注意）。

例えば$X_i=\{1,2,3,4\}$、$X_j=\{2,4,5,6,7\}$の場合は下図のように節点が挿入される。

この変形をステップ3.の条件に当てはまるすべての節点に対して行えば、nice tree-decompositionの3つ目の条件が満たされる。またこの変形は木分解の条件を保ち、幅も変化しない。また、集合$X_i$、$X_j$の要素数は木分解の幅+1以下なので、1つの親と子の組$(X_i,X_j)$に対してステップ3.の変形を行うことで増える節点数は、高々木分解の幅×2+1である。よって幅を定数とみれば、ステップ3.終了後の節点数は$O(|X|)$である。また、幅を定数とみればステップ3.全体でかかる時間計算量も$O(|X|)$である。

以上より、ステップ1、2、3によって、与えられた木分解$(X,T)$から同じ幅で節点数$O(|X|)$のnice tree-decompositionが$O(|X|)$時間で得られることがわかる。$\Box$

3. Nice Tree-decomposition上のDP

 木幅が定数で抑えられるグラフ$G=(V,E)$が与えられたとします。すると、1章で述べた通り、幅最小の木分解$(X,T)$を$O(|V|)$時間で得ることができます。また、2章の補題より$(X,T)$と同じ幅のnice tree-decompositionを$O(|X|)$時間で得ることができます。ここで、$|X|=O(|V|)$なので、これらを合わせることで合計$O(|V|)$時間で節点数$O(|V|)$で幅最小のnice tree-decompositionを得ることができます。

さて、幅最小のnice tree-decompositionが線形時間で得られることがわかったので、以下ではいよいよnice tree-decomposition上のDPによって最大独立集合問題が解けることを紹介していきます。

まず、最大独立集合問題に限らず木分解上でのDPは、次のように行われます。

•  木分解$(X,T)$に対して、適当な節点$X_r\in X$を選んで$T$の根と定める*6
• $T$の各節点$X_i\in X$に対して、グラフ$G_i$を、$X_i$とその子孫全体の和集合を頂点集合としてもつ$G$の誘導部分グラフ*7と定める
• $G$について解きたい問題を、各$G_i$について解くことで最終的に（$G_r=G$なので）$G$についても解く
• $X_i$が子$X_{i_1}, X_{i_2}, ..., X_{i_p}$を持っていたとき、$G_i$について解きたい問題を$G_{i_1}, G_{i_2}, ..., G_{i_p}$について解いた結果を用いて解く

上のDPについて、少し疑問を抱く方もいるかもしれません。つまり、$G_i$について解きたい問題を、$G_{i_1}, G_{i_2}, ..., G_{i_p}$について解いた結果を用いて簡単に解けるのでしょうか？

 $G_i$のある2つの子$G_{i_k}$と$G_{i_l}$の両方に含まれる頂点$u$が存在したとします。このとき、$u$は$X_i$にも必ず含まれます。なぜかというと、$u$を含む$T$の節点全体は連結なので、$X_{i_k}$またはその子孫と、$X_{i_l}$またはその子孫を結ぶ道上にある$X_i$にも$u$が含まれるからです。

また、$G_i$に含まれる辺は、$G_{i_1}, G_{i_2}, ..., G_{i_p}$に含まれる辺か、両端点が$X_i$に含まれる辺のどちらかです。なぜかというと、$G_i$のある辺の2端点を$u,v$とすると、$X_i$またはその子孫で$u$を含むもの、$v$を含むものが少なくとも1つずつあります。また、$u$と$v$の間には辺があるので、$T$は$u,v$を同時に含む節点を持ちます。ここで、$T$上で$u$を含む節点全体、$v$を含む節点全体はそれぞれ連結なので、$X_i$またはその子孫で$u,v$を両方とも含むものが必ず存在します。つまり、辺$(u,v)$は$G_{i_1}, G_{i_2}, ..., G_{i_p}$のいずれかに含まれるか、端点$u,v$が$X_i$に含まれるかのどちらかが成り立ちます。

よって、$G_i$についての問題を$G_{i_1}, G_{i_2}, ..., G_{i_p}$についての結果を用いて解く際に、頂点の重複や新しく追加される辺という意味で考慮しなくてはいけないのは$X_i$まわりだけなので、$X_i$のサイズが小さい（つまり木分解の幅が小さい）なら高速にDPをまわして解くことができます。これが木分解上のDPの強みです。

では、実際に最大独立集合問題に対するnice tree-decomposition上でのDPを見ていきましょう。

 最大独立集合問題に対するDP

 nice tree-decomposition$(X,T)$が与えられたとする。$T$の節点$X_i$とその部分集合$S\subseteq X_i$に対して、$A[i,S]$を$G_i$の独立集合$I$のうち$I\cap X_i=S$を満たすものの最大サイズと定める。$A[i,S]$を次のように更新していく。なお$X_i$の子は1つの場合$X_j$、2つの場合$X_j$、$X_k$と表すことにする。また、$X_i$がintrodece、forgetのときの$X_i$と$X_j$の差となる頂点を$v$とする。

・$X_i$が葉の場合：　$\begin{aligned}A[i,S]=\begin{cases}|S|&(\text{Sは独立集合})\\ -\infty&(\mathrm{otherwise}) \end{cases} \end{aligned}$

 

・$X_i$がjoinの場合：　$A[i,S]=A[j,S]+A[k,S]-|S|$

 

・$X_i$がintroduceの場合：　$\begin{aligned}A[i,S]=\begin{cases}A[j,S]&(v\notin S)\\ A[j,S\setminus\{v\}]+1&(v\in S, v\text{と}S\setminus\{v\}\text{の頂点を結ぶ辺がない})\\ -\infty&(\mathrm{otherwise}) \end{cases} \end{aligned}$

 

・$X_i$がforgetの場合：　$A[i,S]=\mathrm{max}\{A[j,S],A[j,S\cup \{v\}]\}$

$X_i$が葉、forgetの場合の式については少し考えれば成り立つことがわかると思います。$X_i$がjoinの場合の式は、$G_j$のうち$X_i$に含まれない頂点と、$G_k$のうち$X_i$に含まれない頂点との間に辺がないことから成り立ちます。また、$X_i$がintroduceで、$v\in S$の場合については、$G_i$のうち$X_i$に含まれない頂点と$v$の間には辺がないことに注意すると、$v$と$S\setminus \{v\}(\subseteq X_i)$との間に辺がなければ、$v$と$I\cap X_j=S\setminus\{v\}$を満たす$G_j$の独立集合$I$との間にも辺がないので、$A[i,S]=A[j,S\setminus\{v\}]+1$が成り立ちます。

与えられたnice tree-decomposition$(X,T)$の幅が定数$t$、$T$の節点数が$O(|V|)$だとします。すると、このDPの時間計算量は、定数時間で終わる更新を$O(2^{t+1}|V|)$回行うので、合計$O(|V|)$時間かかります。よって、（木幅が定数で抑えられるグラフに対して）幅最小のnice tree-decompositionが線形時間で得られることもあわせて、最大独立集合問題が線形時間で解けることが示されました。

4. おまけ

前の章で、木幅が定数で抑えられるグラフに対して最大独立集合問題が線形時間で解けることを示しました。実は、もっと一般的に次のような事実が成り立ちます。

定理（Courcelle 1990）

 木幅が定数で抑えられるグラフと単項二階論理式で表現できるグラフについての命題が与えられたとき、グラフが命題を満たすかどうかを線形時間で判定できる

 （グラフについての）単項二階論理式とは次の表現を組み合わせて記述できる論理式のことです。

• 論理結合子$\land, \lor, \to, \lnot, =, \neq$
• 頂点、辺に関する量化子$\forall, \exists$
• 述語adj($u,v$)（$u$と$v$の間に辺があるなら1を、ないなら0を返す）
• 述語inc($e,v$)（$v$が$e$の端点なら1を、そうでないなら0を返す）
• 頂点集合、辺集合に関する量化子$\forall, \exists$
• 頂点集合、辺集合に関する$\in, \subseteq$

例えば、グラフが二部グラフである、独立集合である、閉路がある、3彩色可能、などの命題は単項二階論理式で表現可能です。

Coucelleの定理については証明とかも追ってなくてあまりよく知らないので、そのうちちゃんと勉強したいなと思います。

*1:なぜ1を引いているのかというと、木の木幅を1にするためです。

*2:外平面的グラフとは、すべての頂点が外面に面していて、かつ辺は交差しないような平面埋め込みをもつグラフです。例えば木分解の例のところで登場したグラフは外平面的グラフです。

*3:ならない人もいるかもしれません。

*4:nice tree-decompositionに変形せずにそのままDPをする場合の解法はWikipediaに漸化式などが載っています。この漸化式も本質的にはnice tree-decompositionに変形してからDPする場合の漸化式と同じです。

*5:葉と根は必ず空集合という条件を定義に含む流儀などもありますが、今回はそれは採用しませんでした。

*6:nice tree-decompositionに変形した場合はすでに根が定まっています。

*7:$G'$が$G$の誘導部分グラフであるとは、$G'$が$G$の部分グラフであり、かつ両端点がどちらも$G'$に含まれるような$G$の辺はすべて$G'$にも含まれるグラフのことをいいます