木分解

グラフ理論において、木分解とはグラフから木へのマッピングであり、木幅を定義してグラフの上のある種の計算機科学の問題を高速に解くために使われる。

8点のグラフとそのサイズ6の木分解。グラフの各辺に対して、それがつなぐ2点は木のあるノードに同時に含まれている。グラフの各頂点について、それが含まれているノードは木の連結な部分木をなす。木の各ノードは高々3点しか含まないので、この木分解の木幅は2である。

機械学習では、木分解はjunction tree、clique tree、join treeとも呼ばれ、確率伝搬法や制約充足問題、クエリ最適化、en:matrix decompositionのような問題で重要な役割を果たす。

木分解の概念は最初にRudolf Halin (1976)により導入された。後にNeil Robertson and Paul Seymour (1984)により再発見され、以降他の多数の研究者たちに研究されている。

定義

直観的には、木分解は与えられたグラフGの頂点をある一つの木の部分木として表現する。元のグラフGにおいて2つの頂点が隣接するのは対応する部分木が共通部分を持つときに限る。それゆえ、Gは部分木達の交差グラフの部分グラフをなす。交差グラフそのものは弦グラフである。

それぞれの部分木はグラフの頂点に木のノードの集合を割り当てる。このことを形式的に定義すると、木のノードひとつひとつを、それに関連付けられたグラフの頂点の集合として表現する。そのため、グラフG = (V, E)が与えられたとき、木分解はペア(X, T)である。ここで、X = {X₁, ..., X_n} はVの部分集合族で、Tは頂点がVの部分集合X_iであるような木であり、以下の性質を満たす:

1. 全ての集合X_iの和集合はVに等しい。つまり、それぞれの頂点は少なくとも一つの木のノードに割り当てられている。
2. グラフの各辺(v, w) に対して、vとwの両方を含む部分集合 X_i が少なくとも一つ存在する。つまり、グラフの中で頂点が隣接するのは対応する部分木が共通のノードを持つ場合に限られる。
3. X_i と X_j が両方とも頂点vを含む場合、X_i と X_j の間の(一意な)パスに含まれる全てのノードX_kもvを含む。つまり、vに関連付けられたノードたちはTの連結な部分集合をなす。これはcoherenceやrunning intersection propertyとしても知られている。これは、「$X_{i}$, $X_{j}$, $X_{k}$がノードで、$X_{k}$が$X_{i}$ から $X_{j}$へのパス上にあるならば、$X_{i}\cap X_{j}\subseteq X_{k}$である」という条件と同値である。

木分解は一意には定まらない。例えば、自明な木分解として、全ての頂点を含む単一のノードからなる木分解を考えることができる。

台となる木が道グラフであるような木分解を道分解と呼ぶ。このような特殊なタイプの木分解から得られる幅のパラメータは道幅として知られている。

木幅kの木分解(X, T = (I, F))は、$\forall i\in I:|X_{i}|=k+1$と$\forall (i,j)\in F:|X_{i}\cap X_{j}|=k$を満たすときsmoothであるという。

木幅

詳細は「en:Treewidth」を参照

木分解の幅はその最大の集合X_iの大きさ引く1である。グラフGの木幅 tw(G)はすべての可能なGの木分解の幅の最小値である。この定義では、木の木幅を1とするために最大の集合の大きさから1を引いている。木幅は木分解以外の構造からも定義することができる。たとえば弦グラフやbrambles、havensなどである。

与えられたグラフGの木幅が与えられた上限k以下であるかどうかを決定する問題はNP完全である。しかし、kが固定された定数である場合、木幅kのグラフの認識と、幅kの木分解の構成は線型時間で可能である。時間計算量はkについては指数関数的に増加する。

動的計画法

1970年代の始めに、グラフの上の広い範囲の組合せ最適化問題が、グラフの次元(木幅に関係するパラメータ)が制限されている場合には動的計画法によって効率的に解けることが知られていた。その後、多くのNP完全なアルゴリズム的問題が固定された木幅のグラフに対して木分解を用いた動的計画法で効率的に解けることを、1980年代の終わりに数人の研究者が独立に発見した。

例として、木幅kのグラフの最大独立集合を見つける問題を考える。この問題を解くために、木分解のノードを任意に一つ選んで根とする。木分解のノードX_iに対して、D_iをX_iの下のノードX_j全体の和集合とする。独立集合S ⊂ X_iに対して、A(S,i)をD_iの独立集合Iであって、 I ∩ X_i = Sを満たす最大のもののサイズとする。同様に、隣接するノードX_i , X_j(X_jの方が根に近い)と独立集合S ⊂ X_i ∩ X_jに対して、B(S,i,j)をD_iの独立集合Iであって、 I ∩ X_i ∩ X_j = Sを満たす最大のもののサイズとする。AとBは木をボトムアップにたどることによって以下のように計算することができる:

$A(S,i)=|S|+\sum _{j}\left(B(S\cap X_{j},j,i)-|S\cap X_{j}|\right)$

$B(S,i,j)=\max _{S'\subset X_{i} \atop S=S'\cap X_{j}}A(S',i)$

ここで、$A(S,i)$の式における和は$X_{i}$の子ノード全体をわたる。

各ノードと辺において、A(S,i)やB(S,i,j)を計算すべき集合Sの個数は高々2^k+1である。そのため、kが定数ならば、1ノードおよび1辺あたりの計算は定数時間でできる。最大独立集合の大きさは根のノードに格納されている最大の値であり、最大独立集合自身も(普通の動的計画法のアルゴリズムのように)最大値からバックトラックを行うことで計算できる。そのため、決められた木幅のグラフの最大独立集合問題は線形時間で解ける。類似のアルゴリズムによって、他の多くのグラフの問題を解くことができる。

この動的計画法によるアプローチは、機械学習において、決められた木幅のグラフにおける確率伝搬法を行うen:junction tree algorithmに用いられる。また木幅を計算し木分解を構成するためにも用いられる。典型的には、そのようなアルゴリズムは最初に木幅を近似し、その近似した木幅の木分解を構成し、次にその木分解の上で動的計画法を行うことで正確な木幅を計算する。

参考文献

• Arnborg, S.; Corneil, D.; Proskurowski, A. (1987), “Complexity of finding embeddings in a k-tree”, SIAM Journal on Matrix Analysis and Applications 8 (2): 277–284, doi:10.1137/0608024 .
• Arnborg, S.; Proskurowski, A. (1989), “Linear time algorithms for NP-hard problems restricted to partial k-trees”, Discrete Applied Mathematics 23 (1): 11–24, doi:10.1016/0166-218X(89)90031-0 .
• Bern, M. W.; Lawler, E. L.; Wong, A. L. (1987), “Linear-time computation of optimal subgraphs of decomposable graphs”, Journal of Algorithms 8 (2): 216–235, doi:10.1016/0196-6774(87)90039-3 .
• Bertelé, Umberto; Brioschi, Francesco (1972), Nonserial Dynamic Programming, Academic Press, ISBN 0-12-093450-7 .
• Bodlaender, Hans L. (1988), “Dynamic programming on graphs with bounded treewidth”, Proc. 15th International Colloquium on Automata, Languages and Programming, Lecture Notes in Computer Science, 317, Springer-Verlag, pp. 105–118, doi:10.1007/3-540-19488-6_110 .
• Bodlaender, Hans L. (1996), “A linear time algorithm for finding tree-decompositions of small treewidth”, SIAM Journal on Computing 25 (6): 1305–1317, doi:10.1137/S0097539793251219 .
• Diestel, Reinhard (2005), Graph Theory (3rd ed.), Springer, ISBN 3-540-26182-6, http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/ .
• Halin, Rudolf (1976), “S-functions for graphs”, Journal of Geometry 8: 171–186, doi:10.1007/BF01917434 .
• Robertson, Neil; Seymour, Paul D. (1984), “Graph minors III: Planar tree-width”, Journal of Combinatorial Theory, Series B 36 (1): 49–64, doi:10.1016/0095-8956(84)90013-3 .