木分解

グラフ理論において、木分解とはグラフから木へのマッピングであり、を定義してグラフの上のある種の計算機科学の問題を高速に解くために使われる。
機械学習では、木分解はjunction tree、clique tree、join treeとも呼ばれ、確率伝搬法や制約充足問題、クエリ最適化、のような問題で重要な役割を果たす。
木分解の概念は最初ににより導入された。後ににより再発見され、以降他の多数の研究者たちに研究されている。
定義.
直観的には、木分解は与えられたグラフ"G"の頂点をある一つの木の部分木として表現する。元のグラフ"G"において2つの頂点が隣接するのは対応する部分木が共通部分を持つときに限る。それゆえ、"G"は部分木達の交差グラフの部分グラフをなす。交差グラフそのものは弦グラフである。
それぞれの部分木はグラフの頂点に木のノードの集合を割り当てる。このことを形式的に定義すると、木のノードひとつひとつを、それに関連付けられたグラフの頂点の集合として表現する。そのため、グラフ"G" = ("V", "E")が与えられたとき、木分解はペア("X", "T")である。ここで、"X" = {"X"1, ..., "X""n"} は"V"の部分集合族で、"T"は頂点が"V"の部分集合"X""i"であるような木であり、以下の性質を満たす:
木分解は一意には定まらない。例えば、自明な木分解として、全ての頂点を含む単一のノードからなる木分解を考えることができる。
台となる木が道グラフであるような木分解を道分解と呼ぶ。このような特殊なタイプの木分解から得られる幅のパラメータは道幅として知られている。
木幅"k"の木分解("X", "T" = ("I", "F"))は、formula_8とformula_9を満たすとき"smooth"であるという。
木幅.
木分解の"幅"はその最大の集合"X""i"の大きさ引く1である。グラフ"G"の木幅 tw("G")はすべての可能な"G"の木分解の幅の最小値である。この定義では、木の木幅を1とするために最大の集合の大きさから1を引いている。木幅は木分解以外の構造からも定義することができる。たとえば弦グラフや、などである。
与えられたグラフ"G"の木幅が与えられた上限"k"以下であるかどうかを決定する問題はNP完全である。しかし、"k"が固定された定数である場合、木幅"k"のグラフの認識と、幅"k"の木分解の構成は線型時間で可能である。時間計算量は"k"については指数関数的に増加する。
動的計画法.
1970年代の始めに、グラフの上の広い範囲の組合せ最適化問題が、グラフの"次元"(木幅に関係するパラメータ)が制限されている場合には動的計画法によって効率的に解けることが知られていた。その後、多くのNP完全なアルゴリズム的問題が固定された木幅のグラフに対して木分解を用いた動的計画法で効率的に解けることを、1980年代の終わりに数人の研究者が独立に発見した。
例として、木幅"k"のグラフの最大独立集合を見つける問題を考える。この問題を解くために、木分解のノードを任意に一つ選んで根とする。木分解のノード"Xi"に対して、"Di"を"Xi"の下のノード"Xj"全体の和集合とする。独立集合"S" ⊂ "Xi"に対して、"A"("S","i")を"Di"の独立集合"I"であって、
"I" ∩ "Xi" = "S"を満たす最大のもののサイズとする。同様に、隣接するノード"Xi" , "Xj"("Xj"の方が根に近い)と独立集合"S" ⊂ "Xi" ∩ "Xj"に対して、"B"("S","i","j")を"Di"の独立集合"I"であって、
"I" ∩ "Xi" ∩ "Xj" = "S"を満たす最大のもののサイズとする。"A"と"B"は木をボトムアップにたどることによって以下のように計算することができる:
ここで、formula_12の式における和はformula_1の子ノード全体をわたる。
各ノードと辺において、"A(S,i)"や"B(S,i,j)"を計算すべき集合"S"の個数は高々2"k"+1である。そのため、"k"が定数ならば、1ノードおよび1辺あたりの計算は定数時間でできる。最大独立集合の大きさは根のノードに格納されている最大の値であり、最大独立集合自身も(普通の動的計画法のアルゴリズムのように)最大値からバックトラックを行うことで計算できる。そのため、決められた木幅のグラフの最大独立集合問題は線形時間で解ける。類似のアルゴリズムによって、他の多くのグラフの問題を解くことができる。
この動的計画法によるアプローチは、機械学習において、決められた木幅のグラフにおける確率伝搬法を行うに用いられる。また木幅を計算し木分解を構成するためにも用いられる。典型的には、そのようなアルゴリズムは最初に木幅を近似し、その近似した木幅の木分解を構成し、次にその木分解の上で動的計画法を行うことで正確な木幅を計算する。